#include <vector>
using namespace std;

/*
 * 演算法 / Algorithm:
 * 對每個 g 用「兩數皆被 g 整除」的數對數 (c*(c-1)/2)，配合容斥算出 gcd 恰為 g 的數量，
 * 再前綴和 + 二分搜尋回答查詢。/ Count pairs both divisible by g, inclusion-exclusion to get
 * exact-gcd counts, prefix-sum, then binary search per query.
 */
class Solution {
public:
    vector<int> gcdValuesForQueries(vector<int>& nums, vector<int>& queries) {
        // *max_element 回傳最大值的迭代器，解參考取值 / max value in nums
        int maxV = *max_element(nums.begin(), nums.end());

        // vector<int> 自動初始化為 0 / frequency array, index = value
        vector<int> freq(maxV + 1, 0);
        for (int v : nums)                          // range-for：逐一取出元素 / iterate values
            freq[v]++;                              // 該值計數 +1 / count this value

        // long long 防溢位：數對數可達 ~5e9 / avoid int overflow on pair counts
        vector<long long> exact(maxV + 1, 0);       // exact[g] = # pairs with gcd == g
        for (int g = maxV; g >= 1; --g) {           // 由大到小 / descend for inclusion-exclusion
            long long c = 0;                        // # elements divisible by g
            for (int m = g; m <= maxV; m += g)      // g 的倍數 / multiples of g
                c += freq[m];                       // 累加出現次數 / sum frequencies
            long long both = c * (c - 1) / 2;       // 兩數皆整除的數對 / pairs both divisible by g
            for (int m = 2 * g; m <= maxV; m += g)  // 扣掉更大倍數的 gcd / subtract larger-multiple gcds
                both -= exact[m];
            exact[g] = both;                        // gcd 恰為 g / gcd exactly g
        }

        // 前綴和：prefix[g] = gcd <= g 的數對數 / cumulative pair counts
        vector<long long> prefix(maxV + 1, 0);
        long long run = 0;
        for (int g = 1; g <= maxV; ++g)             // 由小到大累加 / accumulate ascending
            prefix[g] = (run += exact[g]);

        vector<int> ans;                            // 結果 / result
        ans.reserve(queries.size());               // 預留空間避免重複配置 / preallocate for speed
        for (long long q : queries) {               // 逐個查詢 / for each query index
            // lower_bound 找第一個 prefix[g] > q 的位置 / first g with prefix[g] > q
            int lo = 1, hi = maxV;                  // 在 gcd 值域上二分 / binary search over gcd values
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;       // 中點 / midpoint
                if (prefix[mid] > q) hi = mid;      // 夠大往左 / enough, shrink right bound
                else lo = mid + 1;                  // 太小往右 / too small, move up
            }
            ans.push_back(lo);                      // 加入答案 / append answer
        }
        return ans;
    }
};