var n,m,i,j1,j2,j3,j4,j5,aux:longint;
    k,p:integer;
    v:array [1..300100] of longint;
    schimb:boolean;
begin
 assign(input,'tricouri.in'); reset (input);
 assign(output,'tricouri.out'); rewrite (output);
  readln(n,m);
  for i:=1 to n do read(v[i]);
  repeat
   schimb:=false;
   for i:=1 to n-1 do
    if v[i]<v[i+1] then begin
     aux:=v[i]; v[i]:=v[i+1]; v[i+1]:=aux; schimb:=true;
    end;
  until not schimb;
  for i:=1 to m do begin
   read(k,p); schimb:=false;
   case k of
    1:begin
       for j1:=1 to n do
        if v[j1] mod p=0 then begin
         writeln(v[j1]); schimb:=true; break;
        end;
       if not schimb then writeln(-1);
      end;
    2:begin
       for j1:=1 to n do begin
        for j2:=1 to n do
         if (j1<>j2) and ((v[j1]+v[j2]) mod p=0) then begin
          writeln(v[j1]+v[j2]); schimb:=true; break;
         end;
        if schimb then break;
       end;
       if not schimb then writeln(-1);
      end;
    3:begin
       for j1:=1 to n do begin
        for j2:=1 to n do begin
         for j3:=1 to n do
          if (j2<>j3) and (j1<>j2) and ((v[j1]+v[j2]+v[j3]) mod p=0) then begin
           writeln(v[j1]+v[j2]+v[j3]); schimb:=true; break;
          end;
         if schimb then break;
        end;
        if schimb then break;
       end;
       if not schimb then writeln(-1);
      end;
    4:begin
       for j1:=1 to n do begin
        for j2:=1 to n do begin
         for j3:=1 to n do begin
          for j4:=1 to n do
           if (j3<>j4) and (j2<>j3) and (j1<>j2) and ((v[j1]+v[j2]+v[j3]+v[j4]) mod p=0) then begin
            writeln(v[j1]+v[j2]+v[j3]+v[j4]); schimb:=true; break;
           end;
          if schimb then break;
         end;
         if schimb then break;
        end;
        if schimb then break;
       end;
       if not schimb then writeln(-1);
      end;
    5:begin
       for j1:=1 to n do begin
        for j2:=1 to n do begin
         for j3:=1 to n do begin
          for j4:=1 to n do begin
           for j5:=1 to n do
            if (j4<>j5) and (j3<>j4) and (j2<>j3) and (j1<>j2) and ((v[j1]+v[j2]+v[j3]+v[j4]+v[j5]) mod p=0) then begin
             writeln(v[j1]+v[j2]+v[j3]+v[j4]+v[j5]); schimb:=true; break;
            end;
           if schimb then break;
          end;
          if schimb then break;
         end;
         if schimb then break;
        end;
        if schimb then break;
       end;
       if not schimb then writeln(-1);
      end;
   end;
  end;
 close(input); close(output);
end.