#include<stdio.h>
int main()
{long n,i,v[5],m,k,p,s,smax,maxpar=0,j,r,x;
FILE *f=fopen("tricouri.in","r");
FILE *g=fopen("tricouri.out","w");
fscanf(f,"%ld %ld",&n,&m);
for (i=1;i<=5;i++) {v[i]=0;}
for (i=1;i<=n;i++)
	{fscanf(f,"%ld",&x);
	if (x>=v[1]) {v[5]=v[4]; v[4]=v[3];v[3]=v[2]; v[2]=v[1]; v[1]=x;}
	else if (x>=v[2]) {v[5]=v[4]; v[4]=v[3]; v[3]=v[2]; v[2]=x;}
	else if (x>=v[3]){v[5]=v[4]; v[4]=v[3]; v[3]=x;}
	else if (x>=v[4]){v[5]=v[4]; v[4]=x;}
	else if(x>=v[5]) v[5]=x;
	if (x%2==0) if (x>maxpar) maxpar=x;}
for (j=1; j<=m;j++)
	{fscanf(f,"%ld %ld",&k,&p);
	switch (k)
		{case 1:{smax=0;
					if (p==2) smax=maxpar;
					else for (i=1;i<=5;i++)
							 if (v[i]%p==0&&v[i]>smax) smax=v[i];
					break;}
		case 2:{ smax=0;
					s=v[1]+v[2];
					if (s%p==0) smax=s;
					s=v[1]+v[3];
					if (smax==0) if (s%p==0) smax=s;
					s=v[1]+v[4];
					if (smax==0) if (s%p==0) smax=s;
					s=v[1]+v[5];
					if (smax==0) if (s%p==0) smax=s;
					s=v[2]+v[3];
					if (smax==0) if (s%p==0) smax=s;
					s=v[2]+v[4];
					if (smax==0) if (s%p==0) smax=s;
					s=v[2]+v[5];
					if (smax==0&&s%p==0) smax=s;
					s=v[3]+v[4];
					if (smax==0&&s%p==0) smax=s;
					s=v[3]+v[5];
					if (smax==0&&s%p==0) smax=s;
					s=v[4]+v[5];
					if (smax==0&&s%p==0) smax=s;
						break;}
		case 3:{s=v[1]+v[2]+v[3];   smax=0;
					if (s%p==0) if(s>smax) smax=s;
					if (smax==0) {s=v[1]+v[2]+v[4];
										if (s%p==0) smax=s; }
					if (smax==0) {s=v[1]+v[2]+v[5];
										if (s%p==0) smax=s;}
					if (smax==0) {s=v[2]+v[3]+v[4];
										if (s%p==0) smax=s;}
					if (smax==0){s=v[2]+v[3]+v[5];
										if (s%p==0) smax=s;}
					if (smax==0){s=v[3]+v[4]+v[5];
										if (s%p==0) smax=s;}
					break;}
		case 4:{s=v[1]+v[2]+v[3]+v[4]; smax=0;
					if (s%p==0)smax=s;
					if (smax==0) {s=v[1]+v[2]+v[3]+v[5];
										if (s%p==0) smax=s;}
					if (smax==0) {s=v[2]+v[3]+v[4]+v[5];
										if (s%p==0) smax=s;}
					break;}
		case 5: {s=v[1]+v[2]+v[3]+v[4]+v[5];smax=0;
					if (s%p==0) smax=s;               break;}
					}
		if (smax==0)fprintf(g,"-1\n");
		else fprintf(g,"%ld\n",smax);}
fclose(f);
fclose(g);
return 0;}