#include<stdio.h>
FILE *f,*g;
int main()
{
long a[200],max,n,x;
int m,k,p,i,j=1,ii,jj,ij;
f=fopen("tricouri.in","r");
g=fopen("tricouri.out","w");

fscanf(f,"%ld%d",&n,&m);
for(i=1;i<=n;i++)
 fscanf(f,"%ld",&a[i]);

while(j==1)
{j=0;
 for(i=1;i<=n-1;i++)
  if(a[i]<a[i+1]) {ij=a[i]; a[i]=a[i+1]; a[i+1]=ij; j=1;}
 }
for(x=1;x<=m;x++)
{fscanf(f,"%d%d",&k,&p);
 max=0;
 if(k==1)
	for(i=1;i<=n;i++)
	 if(a[i]%p==0) {max=a[i];i=n;}
 if(k==2)
	for(i=1;i<=n-1;i++)
	 for(j=i+1;j<=n;j++)
	  if((a[i]+a[j])%p==0) {max=a[i]+a[j]; j=n; i=n-1;}
 if(k==3)
	for(i=1;i<=n-2;i++)
	 for(j=i+1;j<=n-1;j++)
	  for(ii=j+1;ii<=n;ii++)
	   if((a[i]+a[j]+a[ii])%p==0) {max=a[i]+a[j]+a[ii]; ii=n; j=n-1; i=n-2;}
 if(k==4)
	for(i=1;i<=n-3;i++)
	 for(j=i+1;j<=n-2;j++)
	  for(ii=j+1;ii<=n-1;ii++)
	   for(jj=ii+1;jj<=n;jj++)
	    if((a[i]+a[j]+a[ii]+a[jj])%p==0) {max=a[i]+a[j]+a[ii]+a[jj]; jj=n; ii=n-1; j=n-2; i=n-3;}
 if(k==5)
	for(i=1;i<=n-4;i++)
	 for(j=i+1;j<n-3;j++)
	  for(ii=j+1;ii<=n-2;ii++)
	   for(jj=ii+1;jj<=n-1;jj++)
	    for(ij=jj+1;ij<=n;ij++)
	     if((a[i]+a[j]+a[ii]+a[jj]+a[ij])%p==0) {max=a[i]+a[j]+a[ii]+a[jj]+a[ij]; ij=n; jj=n-1; ii=n-2; j=n-3; i=n-4;}



 if(max==0) max=-1;
 fprintf(g,"%d\n",max);
}
fcloseall();
return 0;
}