Code : Sakurako's Test

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Can median be <= mid?
    auto possible = [&](int mid, int x) {
        vector<int> freq(n + 1, 0);
        for (int i = 0; i < n; i++) {
            freq[a[i] % x]++;
        }
        // Convert to prefix sum.
        for (int i = 1; i <= n; i++) {
            freq[i] += freq[i - 1];
        }
        return freq[mid] >= (n + 2) / 2;
    };

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;

        int low = 0, high = n, res = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (possible(mid, x)) {
                res = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        cout << res << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> pfreq(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pfreq[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        pfreq[i] += pfreq[i - 1];
    }

    auto get_sum = [&](int l, int r) {
        r = min(r, n);
        return pfreq[r] - (l ? pfreq[l - 1] : 0);
    };

    vector<int> ans(n + 1);
    for (int x = 1; x <= n; x++) {
        int low = 0, high = n, res = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int cnt = 0;
            for (int start = 0; start <= n; start += x) {
                cnt += get_sum(start, start + min(x - 1, mid));
            }
            if (cnt >= (n + 2) / 2) {
                res = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        ans[x] = res;
    }

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;

        cout << ans[x] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}