#include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 int vis[] , n , m , x , k , num[] , dp[][];

 const int INF = ;

 void dfs(int t , int state)

 {

     if(t >= n){

         for(int i= ; i<=;i++)

             if(dp[i][state%i] > state)

                 dp[i][state%i] = state;

         return;

     }

     for(int i=;i<n;i++){

         if(!vis[i]){

             vis[i] = ;

             dfs(t+ , state*+num[i]);

             vis[i] = ;

         }

     }

 }

 int main()

 {

    // freopen("a.in","rb",stdin);

     //cout<<10*9*8*7*6*5*4*3*2*1<<endl;

     while(scanf("%d%d",&n,&m) == ){

         for(int i=;i<n;i++)

             scanf("%d",num+i);

         memset(vis,,sizeof(vis));

         for(int i=;i<=;i++)

             for(int j=;j<=;j++) dp[i][j] = INF;

         for(int i=;i<n;i++){

             if(num[i]){

                 vis[i] = ;

                 dfs(,num[i]);

                 vis[i] = ;

             }

         }

         for(int i=;i<m;i++)

         {

             scanf("%d%d",&x,&k);

             if(dp[k][(((-x)%k)+k)%k] < INF)

                 printf("%d\n",dp[k][(((-x)%k)+k)%k]); //state+x = b*k -> state%k = (-x)%k

             else puts("None");

         }

     }

     return ;

 }