#include<fstream.h>
#include<stdlib.h>
#define NMAX 300001
int v[NMAX];
int fcmp(void const *a,void const *b)
{return *((int *)b)-*((int*)a);}


int main()
{
ifstream fin("tricouri.in");
ofstream fout("tricouri.out");
int n,i,j,s,k,p,m,gata,sol,c,d,e;
fin>>n>>m;
for(i=0;i<n;i++) fin>>v[i];
qsort(v,n,sizeof(v[0]),fcmp);
while(m--){fin>>k>>p;
					 s=0;
					 sol=0;
					 gata=0;
					 switch(k){
					 case 1:for(i=0;i<n&&!gata;i++) if(v[i]%p==0) {s=v[i];
																												 gata=1;
																												}
									if(gata) sol=1;
									break;
					 case 2:for(i=0;i<n-1&&!gata;i++)
											for(j=i+1;j<n&&!gata;j++) {s=v[i]+v[j];
																								 if(s%p==0) gata=1;
																								}
									if(gata) sol=1;
									break;
					 case 3:for(i=0;i<n-2&&!gata;i++)
											for(j=i+1;j<n-1&&!gata;j++)
														for(c=j+1;c<n&&!gata;c++) {s=v[i]+v[j]+v[c];
																											 if(s%p==0) gata=1;
																											}
									if(gata) sol=1;
									break;
					 case 4:for(i=0;i<n-3&&!gata;i++)
											for(j=i+1;j<n-2&&!gata;j++)
														for(c=j+1;c<n-1&&!gata;c++)
																 for(d=c+1;d<n&&!gata;d++) {s=v[i]+v[j]+v[c]+v[d];
																														if(s%p==0) gata=1;
																													 }
									if(gata) sol=1;
									break;
					 case 5:for(i=0;i<n-4&&!gata;i++)
											for(j=i+1;j<n-3&&!gata;j++)
														for(c=j+1;c<n-2&&!gata;c++)
																 for(d=c+1;d<n-1&&!gata;d++)
																			 for(e=d+1;e<n&&!gata;e++)  {s=v[i]+v[j]+v[c]+v[d]+v[e];
																																	 if(s%p==0) gata=1;
																																	}
									if(gata) sol=1;
									break;

						}
					 if(sol) fout<<s<<"\n";
					 else fout<<"-1\n";
					}
return 0;
}