#include<bits/stdc++.h>
using namespace std;
 
 
bool check(vector<int>&v, int x, int m){
    int n = v.size(); int ct = 0;
    for(int k=0;k<=n/x;k++){
        ct += upper_bound(v.begin(),v.end(),k*x+m) - upper_bound(v.begin(),v.end(),k*x-1);
    }
    return ct>=(n+2)/2;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin>>t;
    while(t--){
        int n,q; cin>>n>>q;
        vector<int>v(n);
        for(int i=0;i<n;i++) cin>>v[i];
        sort(v.begin(),v.end());
        vector<int>dp(n+1);
        for(int i=1;i<=n;i++){
            int l = 0, r = i-1;
            while(l<=r){
                int m = l + (r-l)/2;
                if(check(v,i,m)){
                    dp[i] = m; r=m-1;
                }
                else l=m+1;
            }
        }
        while(q--){
            int x; cin>>x;
            cout<<dp[x]<<" ";
        }
        cout<<'\n';
    }
}

Why does this simple code implementing your approach giving TLE

btw Pa_sha orz