#include <bits/stdc++.h>
using namespace std;

ifstream fin("tricouri.in");
ofstream fout("tricouri.out");

long long v[300001], mat[21][20][6], u[21], n, m, nr, p, k, st[6], sk, smax=0;

/*bool suc(){
    if(st[k]>=p-1)
        return 0;

    if(st[k]!=st[k-1]-1){
        sk-=st[k];
        s-=mat[p][st[k]][u[st[k]]];
        u[st[k]]--;
    }
    st[k]++;
    while(st[k]<=p&&u[st[k]]>=mat[p][st[k]][0])
        st[k]++;
    if(st[k]>p) return 0;
    u[st[k]]++;
    s+=mat[p][st[k]][u[st[k]]];
    sk+=st[k];
    return 1;
}*/

int main(){
    ios::sync_with_stdio(0);
    fin.tie(NULL);
    fout.tie(NULL);

    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>v[i];

    sort(v+1, v+n+1);
    /*for(int i=1;i<=n;i++)
        cout<<v[i]<<' ';
    cout<<endl;*/

    for(int i=n;i>0;i--)
        for(int j=2;j<=20;j++)
            if(mat[j][v[i]%j][0]<5)
                mat[j][v[i]%j][++mat[j][v[i]%j][0]]=v[i];


    for(int j=2;j<=20;j++){
        cout<<j<<endl;
        for(int r=0;r<j;r++){
            cout<<j<<' '<<r<<'\n';
            for(int i=1;i<=mat[j][r][0];i++)
                cout<<mat[j][r][i]<<' ';
            cout<<'\n';
        }
    }

    for(int q=1;q<=m;q++){
        fin>>k>>p;

        vector <vector <long long>> dp(k+1, vector<long long>(p, -1));

        dp[0][0]=0;

        for(int r=0;r<p;r++){
            if(mat[p][r][0]){
                long long s=0;
                for(int nr=1;nr<=min(k,mat[p][r][0]);nr++){
                    s+=mat[p][r][nr];
                    for(int i=k;i>=nr;i--){
                        for(int r2=0;r2<p;r2++){
                            if(dp[i-nr][r2]!=-1){
                                if(dp[i][(r*nr+r2)%p]<dp[i-nr][r2]+s)
                                    dp[i][(r*nr+r2)%p]=dp[i-nr][r2]+s;
                            }
                        }
                    }
                }
            }
        }

        fout<<dp[k][0]<<'\n';
        /*s=0;
        smax=-1;
        sk=0;
        k=1;
        st[k]=-1;
        for(int i=0;i<p;i++) u[i]=0;
        //cout<<"nr="<<nr<<" p="<<p<<'\n';
        while(k>0){
            if(k==nr){
                st[k]=p-sk%p;
                if(u[st[k]]<mat[p][st[k]][0]){
                    u[st[k]]++;
                    s+=mat[p][st[k]][u[st[k]]];
                    sk+=st[k];

                    if(s>smax) smax=s;
                    s-=mat[p][st[k]][u[st[k]]];
                    u[st[k]]--;
                    sk-=st[k];
                }
                k--;
            }
            else if(suc()){
                k++;
                st[k]=st[k-1]-1;
            }
            else
                k--;
        }
        fout<<smax<<'\n';*/
    }
    return 0;
}