#include<fstream.h>
long n,m,a[300001],k,p,i,gasit,s,a1,a2,a3,a4,a5;
void quik(long int p,long int q)
{
  long int aux,i,j,t;
   if(p<q)
    {
     i=p;
     j=q;
     t=1;
  do
    {
     if(a[i]>a[j])
      {
       aux=a[i];
       a[i]=a[j];
       a[j]=aux;
       t=!t;
      }
     if(t)
      j--;
       else
      i++;
    }while(i!=j);
   quik(p,i-1);
   quik(i+1,q);
  }
}
int main()
{
  ifstream f("tricouri.in");
  ofstream g("tricouri.out");
   f>>n>>m;
  for(i=1;i<=n;i++)
   f>>a[i];
  quik(1,n);
   for(i=1;i<=m;i++)
    {
     f>>k>>p;
     gasit=0;s=0;
     if(k==1)
      {
       a1=n;
	while(!gasit)
	 {
	  s=0;
	  s=s+a[a1];
	   if(s%p==0&&s!=0)
	   {
	    g<<s<<"\n";
	    gasit=1;
	   }
	  else
	   a1--;
	  if(a1<=0&&gasit==0)
	   {
	    g<<"-1"<<"\n";
	    gasit=1;
	   }
	}
       }
	  if(k==2)
	   {
	    a1=n;a2=n-1;
	     while(!gasit)
	      {
	       s=a[a1]+a[a2];
		if(s%p==0)
		 {
		  g<<s<<"\n";
		  gasit=1;
		 }
		else
		 a2--;
		if(a2<=0)
		 {
		  a1=a1-1;
		  a2=a1-1;
		 }
		if(a1<=0&&a2<=0&&gasit==0)
		 {
		   g<<"-1"<<"\n";
		   gasit=1;
		 }
	       }
	    }
	   if(k==3)
	    {
	     a1=n;a2=n-1;a3=n-2;
	      while(!gasit)
	       {
		s=a[a1]+a[a2]+a[a3];
		 if(s%p==0)
		  {
		    g<<s<<"\n";
		    gasit=1;
		  }
		 else
		  a3--;
		if(a3<=0)
		{
		 a2--;
		 a3=a2-1;
		}
		if(a2<=1)
		 {
		  a1=a1-1;
		  a2=a1-1;
		  a3=a2-1;
		 }
		if(a1<=0&&a2<=0&&a3<=0&&gasit==0)
		 {
		  g<<"-1"<<"\n";
		  gasit=1;
		 }
	       }
	    }
	   if(k==4)
	    {
	     a1=n;a2=n-1;a3=n-2;a4=n-3;
	      while(!gasit)
	       {
		s=a[a1]+a[a2]+a[a3]+a[a4];
		 if(s%p==0)
		  {
		   g<<s<<"\n";
		   gasit=1;
		  }
		else
		 a4--;
		  if(a4<=0)
		  {
		   a3--;
		   a4=a3-1;
		  }
		 if(a3<=1)
		  {
		   a2--;
		   a3=a2-1;
		   a4=a3-1;
		  }
		 if(a2<=2)
		  {
		   a1=a1-1;
		   a2=a1-1;
		   a3=a2-1;
		   a4=a3-1;
		  }
	       if(a1<=0&&a2<=0&&a3<=0&&a4<=0&&gasit==0)
		{
		 g<<"-1"<<"\n";
		 gasit=1;
		}
	     }
	   }
	    if(k==5)
	     {
	      a1=n;a2=n-1;a3=n-2;a4=n-3;a5=n-4;
	       while(!gasit)
		{
		 s=a[a1]+a[a2]+a[a3]+a[a4]+a[a5];
		  if(s%p==0)
		   {
		     g<<s<<"\n";
		     gasit=1;
		   }
		  else
		   a5--;
		  if(a5<=0)
		   {
		    a4--;
		    a5=a4-1;
		   }
		  if(a4<=1)
		   {
		    a3--;
		    a4=a3-1;
		    a5=a4-1;
		   }
		  if(a3<=2)
		   {
		    a2--;
		    a3=a2-1;
		    a4=a3-1;
		    a5=a4-1;
		   }
		 if(a2<=3)
		  {
		    a1--;
		    a2=a1-1;
		    a3=a2-1;
		    a4=a3-1;
		    a5=a4-1;
		  }
		if(a1<=0&&a2<=0&&a3<=0&&a4<=0&&a5<=0&&gasit==0)
		 {
		  g<<"-1"<<"\n";
		  gasit=1;
		 }
	       }
	    }
       }
 return 0;
}