#include <bits/stdc++.h>
using namespace std;
ifstream fin("tricouri.in");
ofstream fout("tricouri.out");
int n, m, k, p, maxi, st[7], a[22][22][7], u[22][22];
void solutie()
{
    int i, r=st[0]%p, poz[22]= {0}, s=0;
    if(a[p][(p-r)%p][0])
    {
        st[k]=(p-r)%p;
        for(i=1; i<=k; i++)
            s+=a[p][st[i]][++poz[st[i]]];
        maxi=max(maxi,s);
    }
    else return;
}
void bk(int nivel)
{
    for(int i=0; i<p; i++)
    {
        st[nivel]=i;
        u[p][i]++;
        if(u[p][i]<=a[p][i][0])
        {
            st[0]+=st[nivel];
            if(nivel==k-1) solutie();
            else bk(nivel+1);
            st[0]-=st[nivel];
        }
        u[p][i]--;
    }
}
int main()
{
    int i, j, z, mini, pozmini, x;
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        fin>>x;
        for(j=2; j<=20; j++)
        {
            if(a[j][x%j][0]<5)
                a[j][x%j][++a[j][x%j][0]]=x;
            else
            {
                mini=INT_MAX;
                for(z=1; z<=a[j][x%j][0]; z++)
                    if(a[j][x%j][z]<mini)
                    {
                        mini=a[j][x%j][z];
                        pozmini=z;
                    }
                a[j][x%j][pozmini]=x;
            }

        }
    }
    for(i=2; i<=20; i++)
        for(j=0; j<i; j++)
            sort(a[i][j]+1,a[i][j]+a[i][j][0]+1,greater<int>());
    for(i=1; i<=m; i++)
    {
        fin>>k>>p;
        if(k==1)
        {
            if(a[p][0][0]) fout<<a[p][0][1]<<'\n';
            else fout<<-1<<'\n';
        }
        else
        {
            maxi=-1;
            bk(1);
            fout<<maxi<<'\n';
        }
    }
    return 0;
}