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<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define REVERSE(x) reverse((x).begin(), (x).end())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << '\n'
#define endl '\n'

constexpr int IINF = (1 << 30) - 1;
constexpr long long LLINF = 1LL << 61;
constexpr double EPS = 1e-10;

constexpr int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
constexpr int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T& a, T b){
    if(b < a){
        a = b;
        return true;
    }
    return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int n, m, t;
    cin >> n >> m >> t;

    lint dp1[20][1000];
    fill(dp1[0], dp1[20], -1LL);

    lint dp2[1000];
    fill(dp2, dp2 + t, -1LL);

    rep(i, n){
        lint a;
        cin >> a;
        chmax(dp1[0][a % t], a);
    }

    rep(i, 19){
        rep(j, t){
            chmax(dp1[i + 1][j], dp1[i][j]);
            rep(k, t){
                if(dp1[i][j] >= 0LL && dp1[i][k] >= 0LL){
                    chmax(dp1[i + 1][(j + k) % t], dp1[i][j] + dp1[i][k]);
                }
            }
        }
    }

    rep(i, 20){
        if(!(m >> i & 1)){
            continue;
        }
        lint dp3[1000];
        rep(j, t){
            dp3[j] = dp2[j];
        }
        rep(j, t){
            chmax(dp3[j], dp1[i][j]);
            rep(k, t){
                if(dp1[i][j] >= 0LL && dp2[k] >= 0LL){
                    chmax(dp3[(j + k) % t], dp1[i][j] + dp2[k]);
                }
            }
        }
        rep(j, t){
            dp2[j] = dp3[j];
        }
    }

    rrep(j, t - 1){
        chmax(dp2[j], dp2[j + 1]);
    }

    int q;
    cin >> q;

    while(q--){
        int a, b;
        cin >> a >> b;
        if(dp2[a] >= 0LL && dp2[a] / t >= b){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }

    cout << flush;

    return 0;
}