#include<stdio.h>
#define NMAX 300001

int v[NMAX]={0},n;

void poz(int ls,int ld,int &piv){
int i=ls,j=ld,d=0,t;
while(i<j){
	if(v[i]<v[j]){
		t=v[i];v[i]=v[j];v[j]=t;
		d=1-d;
		}
	i+=d;
	j-=1-d;
	}
piv=i;
}

void qsrt(int st,int dr){
int piv;
if(st<dr){
	poz(st,dr,piv);
	qsrt(st,piv-1);
	qsrt(piv+1,dr);
	}
}

int main(){
struct cer{int k,p;};
freopen("tricouri.in","r",stdin);
freopen("tricouri.out","w",stdout);

cer w[101]={{0,0}};
int m,i,j,k,up,s[6],sm=0,sa,ok,ii,iii,i1,i2,i3,i4,i5;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&v[i]);
for(j=1;j<=m;j++) scanf("%d%d",&w[j].k,&w[j].p);
qsrt(1,n);
for(j=1;j<=m;j++){
	sm=0;ok=0;
	switch (w[j].k){
   //ar trebui cautat binar
	case 1:for(i=1;i<=n&&v[i]>w[j].p;i++);
		   if(i<=n&&v[i]==w[j].p) {ok=1;sm=v[i];}
		   break;
	case 2:for(i=1;i<n&&!ok;i++)
			  for(ii=i+1;ii<=n&&!ok;ii++){
				sm=v[i]+v[ii];
				if(sm%w[j].p==0) ok=1;
				}
		   break;
	case 3:for(i=1;i<n-1&&!ok;i++)
			  for(ii=i+1;ii<n&&!ok;ii++)
				for(iii=ii+1;iii<=n&&!ok;iii++){
					sm=v[i]+v[ii]+v[iii];
					if(sm%w[j].p==0) ok=1;
					}
		   break;
	case 4:for(i1=1;i1<n-2&&!ok;i1++)
			  for(i2=i1+1;i2<n-1&&!ok;i2++)
				for(i3=i2+1;i3<n&&!ok;i3++)
					for(i4=i3+1;i4<=n&&!ok;i4++){
						sm=v[i1]+v[i2]+v[i3]+v[i4];
					if(sm%w[j].p==0) ok=1;
					}
		   break;
	case 5:for(i1=1;i1<n-3&&!ok;i1++)
			  for(i2=i1+1;i2<n-2&&!ok;i2++)
				for(i3=i2+1;i3<n-1&&!ok;i3++)
					for(i4=i3+1;i4<n&&!ok;i4++)
						for(i5=i4+1;i5<=n&&!ok;i5++){
						sm=v[i1]+v[i2]+v[i3]+v[i4]+v[i5];
					if(sm%w[j].p==0) ok=1;
					}
		   break;
	}
	/*
	default:
	k=1;s[k]=0;
	while(k){
		up=0;
			s[k]++;
			if(s[k]<n-w[j].k+k)	up=1;
	   //	if(v[s[1]]*w[j].k<sm) break;
		if(up)
			if(k==w[j].k){
				sa=0;
				for(i=1;i<=k;i++) sa+=v[s[i]];
				if(sa%w[j].p==0) {
					ok=1;
					if(sm<sa) sm=sa;
					break;
					}
			   //	if(ok&&sm>1.5*sa) break;
				}
			else {k++;s[k]=s[k-1];}
		else k--;
		}
	} */
	if(ok) printf("%d\n",sm);
	else printf("-1\n");
	}
return 0;
}