#include<fstream.h>
#include<stdlib.h>
#define NMAX 300001
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,v[NMAX],i,j,s,k,p,m,gata,sol,c;
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;
						}
					 if(sol) fout<<s<<"\n";
					 else fout<<"-1\n";
					}
return 0;
}