#include<fstream.h>
ifstream f("tricouri.in");
ofstream g("tricouri.out");
long n,a[21][5][20];
int m,p,k,x[6];

void inserare(int r,int q,int x)
{int i,j;
 for(i=0;i<5;i++)
	if(x>a[q][i][r])
	{	for(j=4;j>i;j--)
			a[q][j][r]=a[q][j-1][r];
		a[q][i][r]=x;
		break;
	}
}

void citire()
{int x,i,q,r;
 f>>n>>m;
 for(i=0;i<n;i++)
 {	f>>x;
	for(q=1;q<20;q++)
	{	r=x%q;
		inserare(r,q,x);
	}
 }
}

long calc(int q)
{int s=0,w[21],i;
 for(i=0;i<21;i++)
	w[i]=0;
 for(i=1;i<=q;i++)
 {	s+=a[p][w[x[i]]][x[i]];
	w[x[i]]++;
 }
 return s;
}

void max()
{int q=1,s=0,r[21],i,j,z;
 long Max=0;
 x[q]=-1;
 for(i=0;i<21;i++)
	r[i]=0;
 for(i=0;i<5;i++)
	for(int j=0;j<p;j++)
		if(a[p][i][j]!=0)
			r[j]++;
 while(q!=0)
 {	if(x[q]+1<=(q-1)*p-s && q<=k && x[q]+1<p)
	{	x[q]=x[q]+1;
		if(x[q]<=(q-1)*p-s && r[x[q]]>0)
		{       r[x[q]]--;
			s+=x[q];
			if(q==k && s%p==0)
			{	z=calc(q);
				if(z>Max)
					Max=z;
			}
			else
			{	q++;
				x[q]=-1;
			}
		}
	}
	else
	{       if(x[q]>=0)
		{	r[x[q]]++;
			s-=x[q];
		}
		q--;
		r[x[q]]++;
		s-=x[q];
	}
 }
 if(Max!=0)
	g<<Max<<'\n';
 else
	g<<-1<<'\n';
}

int main()
{int i;
 citire();
 for(i=0;i<m;i++)
 {	f>>k>>p;
	if(k==1)
		if(a[p][0][0]==0)
			g<<-1<<'\n';
		else
			g<<a[p][0][0]<<'\n';
	else
		max();
 }
 g.close();
 return 0;
}