#include <stdio.h>
int a[300001];
int i,i1,i2,i3,i4,i5,m,n,k,p,max;
int main()
{
	freopen("tricouri.in","r",stdin);
	freopen("tricouri.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d",&k,&p);
		max=-1;
		if (k==1)
			for (i1=1;i1<=n;++i1)
				if (a[i1]%p==0 && a[i1]>max) max=a[i1];
		if (k==2)
			for (i1=1;i1<=n;++i1)
				for (i2=i1+1;i2<=n;++i2)
					if ((a[i1]+a[i2])%p==0 && a[i1]+a[i2]>max) max=a[i1]+a[i2];
		if (k==3)
			for (i1=1;i1<=n;++i1)
				for (i2=i1+1;i2<=n;++i2)
					for (i3=i2+1;i3<=n;++i3)
						if ((a[i1]+a[i2]+a[i3])%p==0 && a[i1]+a[i2]+a[i3]>max) max=a[i1]+a[i2]+a[i3];
		if (k==4)
			for (i1=1;i1<=n;++i1)
				for (i2=i1+1;i2<=n;++i2)
					for (i3=i2+1;i3<=n;++i3)
						for (i4=i3+1;i4<=n;++i4)
							if ((a[i1]+a[i2]+a[i3]+a[i4])%p==0 && a[i1]+a[i2]+a[i3]+a[i4]>max) max=a[i1]+a[i2]+a[i3]+a[i4];
		if (k==4)
			for (i1=1;i1<=n;++i1)
				for (i2=i1+1;i2<=n;++i2)
					for (i3=i2+1;i3<=n;++i3)
						for (i4=i3+1;i4<=n;++i4)
							for (i5=i4+1;i5<=n;++i5);
							if ((a[i1]+a[i2]+a[i3]+a[i4]+a[i5])%p==0 && a[i1]+a[i2]+a[i3]+a[i4]+a[i5]>max) max=a[i1]+a[i2]+a[i3]+a[i4]+a[i5];
							if (max==0) max=-1;
		printf("%d\n",max);
	}
	return 0;
}