Intergalactic

///complexitate O(vmax*log(vmax)+n*log(n)+T*log(vmax)*n)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream  fin("intergalactic.in");
ofstream fout("intergalactic.out");
int T, n, k, a[200002], b[200002], aux, p, q, i, j, *x, *y, z;
char ciur[2000002];
long long f(int s){
    ///calculeaza cate perechi au suma <=s
    long long  nr=0;
    int i,j1,j2,js=q;
    for(i=1;i<=p && js>0;i++){
        if(i>=2 && x[i]-x[i-1]<100000){
            while(js>0 && x[i]+y[js]>s)js--;
        }
        else{
            j1=1; j2=js; js=0;
            while(j1<=j2){
                j=(j1+j2)/2;
                if(x[i]+y[j]<=s){
                    js=j;
                    j1=j+1;
                }
                else{
                    j2=j-1;
                }
            }
        }
        nr=nr+js;
    }
    return nr;
}
int main(){
    ciur[1]=1;
    for(i=2;i*i<=2000000;i++){
        if(ciur[i]==0){
            for(j=i*i;j<=2000000;j=j+i){
                ciur[j]=1;
            }
        }
    }
    fin>>n>>T;
    p=0;q=0;
    for(i=1;i<=n;i++){
        fin>>z;
        if(ciur[z]==0){
            p++;a[p]=z;
        }
        else{
            q++;b[q]=z;
        }
    }
    sort(a+1,a+1+p);
    sort(b+1,b+1+q);
    x=a; y=b;
    if(p>q){x=b;y=a;aux=p;p=q;q=aux;}
    for(int t=1;t<=T;t++){
        fin>>k;
        long long k1;
        int s1,s2,s3=0,s;
        s1=x[1]+y[1]; s2=x[p]+y[q];
        while(s1<=s2){
            s=(s1+s2)/2;
            k1=f(s);
            if(k1>=k){
                s3=s;
                s2=s-1;
            }
            else{
                s1=s+1;
            }
        }
        fout<<s3<<"\n";
    }

    return 0;
}