#include<stdio.h>
#define NMAX 300000

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[100]={{0,0}};
int m,i,s,ok,a,b,c,d,e,sm,tst1,tst2;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++) scanf("%d",&v[i]);
for(i=0;i<m;i++) scanf("%d%d",&w[i].k,&w[i].p);
qsrt(0,n-1);
for(i=0;i<m;i++){
	s=0;ok=0;sm=0;tst1=0;
	switch (w[i].k){
   //ar trebui cautat binar
	case 1:a=0;
		   while(v[a]%w[i].p!=0) a++;
		   if(a<n&&v[a]%w[i].p==0) {ok=1;sm=v[a];}
		   break;
	case 2:if(v[0]+v[1]<w[i].p) ;else
		   for(a=0;a<n-1;a++){
			  if(tst1&&v[a]==v[a-1]) continue;
			  tst1=1;
			  if(v[a]+v[a+1]<=sm) break;
			  tst2=0;
			  for(b=a+1;b<n;b++){
				if(tst2&&v[b]==v[b-1]) continue;
				tst2=1;
				s=v[a]+v[b];
				if(s<=sm) break;
				if(s%w[i].p==0&&s>sm) {sm=s;break;}
				}
		   }
		   if(sm) ok=1;
		   break;
	case 3:if(v[0]+v[1]+v[2]<w[i].p) ;else
		   for(a=0;a<n-2;a++){
			  if(v[a]+v[a+1]+v[a+2]<=sm) break;
			  for(b=a+1;b<n-1;b++){
				if(v[a]+v[b]+v[b+1]<=sm) break;
				for(c=b+1;c<n;c++){
					s=v[a]+v[b]+v[c];
					if(s<=sm) break;
					if(s%w[i].p==0&&s>sm) {sm=s;break;}
					}
				}
		   }
		   if(sm) ok=1;
		   break;
	case 4:if(v[0]+v[1]+v[2]+v[3]<w[i].p) ;else
		   for(a=0;a<n-3;a++){
			  if(v[a]+v[a+1]+v[a+2]+v[a+3]<=sm) break;
			  for(b=a+1;b<n-2;b++){
				if(v[a]+v[b]+v[b+1]+v[b+2]<=sm) break;
				for(c=b+1;c<n-1;c++){
					if(v[a]+v[b]+v[c]+v[c+1]<=sm) break;
					for(d=c+1;d<n;d++){
						s=v[a]+v[b]+v[c]+v[d];
						if(s<=sm) break;
						if(s%w[i].p==0&&s>sm) {sm=s;break;}
					}
				}
			  }
		   }
		   if(sm) ok=1;
		   break;
	case 5:if(v[0]+v[1]+v[2]+v[3]+v[4]<w[i].p) ;else
		   for(a=0;a<n-4;a++){
			  if(v[a]+v[a+1]+v[a+2]+v[a+3]+v[a+4]<=sm) break;
			  for(b=a+1;b<n-3;b++){
				if(v[a]+v[b]+v[b+1]+v[b+2]+v[b+3]<=sm) break;
				for(c=b+1;c<n-2;c++){
					if(v[a]+v[b]+v[c]+v[c+1]+v[c+2]<=sm) break;
					for(d=c+1;d<n-1;d++){
						if(v[a]+v[b]+v[c]+v[d]+v[d+1]<=sm) break;
						for(e=d+1;e<n;e++){
						s=v[a]+v[b]+v[c]+v[d]+v[e];
						if(s<=sm) break;
						if(s%w[i].p==0&&s>sm) {sm=s;break;}
						}
					}
				}
			  }
		   }
		   if(sm) ok=1;
		   break;
	}
	if(ok);
	else sm=-1;
	printf("%d\n",sm);
	}
return 0;
}