Problem: A lottery is being held in a corner of the venue of the Aizu festival. Several types of balls are inside the lottery box and each type has its unique integer printed on the surfaces of the balls. An integer T is printed on the lottery box.

In the lottery, you first declare two integers A and B, and draw up to M balls from the box. Let the sum of the integers printed on the balls be S. You can get a wonderful gift if the following two criteria are met: S divided by T gives a remainder greater than or equal to A, and S divided by T gives a quotient (fractional portion dropped) greater than or equal to B.

Write a program to determine if you have any chance of getting the gift given the following information: the number of ball types, ball-type specific integers, the maximum number of balls to be drawn from the box, the integer printed on the lottery box, and two integers declared before drawing. Assume that each ball type has sufficient (≥M) population in the box. Note also that there may be a chance of getting the gift even without drawing any ball.



Input

The input is given in the following format.


N M T
a_1
a_2
:
a_N
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q


The first line provides the number of ball types N(1≤N≤105), the maximum number of balls you can draw from the box M(1≤M≤105), and the integer printed on the box T(1≤T≤1000). Each of the subsequent N lines provides an integer a_i (1≤a_i≤109) printed on the i-th ball type. The next line following these provides the number of declarations Q (1≤Q≤105). Each of the Q lines following this provides a pair of integers A_i (0 ≤ A_i < T), B_i (0 ≤ B_i ≤ 109) that constitute the i-th declaration.

Output

Output a line for each pair of declaration A and B that contains "yes" if there is a chance of getting the gift or "no" otherwise.

Example

Input

3 2 7
8
3
6
5
2 2
3 2
4 1
6 1
6 0


Output

yes
no
yes
no
yes

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
//define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
// 許容する誤差ε
#define EPS (1e-10)
// 2つのスカラーが等しいかどうか
#define EQ(a,b) (abs((a)-(b)) < EPS)
// 2つのベクトルが等しいかどうか
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
//template
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
      }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
//typedef
typedef complex<double> Point;
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;




int a[200000], dp[60][2000], ans[2][2000];
int get_log(int n){
  int res = 0, m = 1;
  while(m < n){m *= 2;res++;}
  return res;
}
signed main(){
  int n, m, t;
  scanf("%lld%lld%lld", &n, &m, &t);
  rep(i,n)scanf("%lld", &a[i]);
  
  fill((int*)dp, (int*)(dp+60), -INF);dp[0][0] = 0;
  rep(i,n)chmax(dp[0][a[i]%t], a[i]);
  int L = get_log(m+2);
  rrep(i,L){
    // rep(j,t)chmax(dp[i][j], dp[i-1][j]);
    rep(j,t){
      rep(k,t){
        int l = (j+k)%t;
        if(dp[i-1][j] == -INF or dp[i-1][k] == -INF)continue;
        chmax(dp[i][l], dp[i-1][j]+dp[i-1][k]);
      }
    }
  }
  rep(i,t)ans[0][i] = -INF;ans[0][0] = 0;
  rep(i,30){
    if((m & (1<<i)) == 0)continue;
    rep(j,t)ans[1][j] = -INF;
    // rep(j,t)chmax(ans[1][j], ans[0][j]);
    // rep(j,t)chmax(ans[1][j], dp[i][j]);
    rep(j,t){
      rep(k,t){
        int l = (j+k)%t;
        if(dp[i][j] == -INF or ans[0][k] == -INF)continue;
        chmax(ans[1][l], dp[i][j]+ans[0][k]);
      }
    }
    swap(ans[0], ans[1]);
  }
  int mx = -INF;
  drep(i,t-2,0){
    chmax(ans[0][i], ans[0][i+1]);
  }
  
  int q;
  scanf("%lld", &q);
  rep(i,q){
    int A, B;
    scanf("%lld%lld", &A, &B);
    if(ans[0][A] != -INF and ans[0][A]/t >= B)cout << "yes" << endl;
    else cout << "no" << endl;
  }
	return 0;
}