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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
 
 
ll N,M,T;
ll POW[21],dp[21][1000],table[1000][2];
 
 
int main(){
    for(int i = 0; i < 21; i++)POW[i] = pow(2,i);
 
    for(int i = 0; i < 21; i++){
        for(int k = 0; k < 1000; k++)dp[i][k] = -1;
    }
 
    scanf("%lld %lld %lld",&N,&M,&T);
 
    ll tmp;
    for(int loop = 0; loop < N; loop++){
        scanf("%lld",&tmp);
        dp[0][tmp%T] = max(dp[0][tmp%T],tmp); //余り毎に最大値を求める
    }
 
    //ダブリング
    for(int i = 0; POW[i+1] <= M;i++){
        for(int a = 0; a < T; a++){
            if(dp[i][a] == -1)continue;
            for(int b = 0; b < T; b++){
                if(dp[i][b] == -1)continue;
                dp[i+1][(a+b)%T] = max(dp[i+1][(a+b)%T],dp[i][a]+dp[i][b]);
            }
        }
    }
 
    int CURRENT = 0,NEXT = 1;
    for(int i = 0; i < T; i++)table[i][CURRENT] = -1;
    ll rest = M;
 
    bool FIRST = true;
    //
    for(int i = 20; i >= 0; i--){
        if(rest < POW[i])continue;
        rest -= POW[i];
 
        if(FIRST){ //初めての場合
            for(int b = 0; b < T; b++){ //dpのループ
                if(dp[i][b] == -1)continue;
 
                table[b][CURRENT] = dp[i][b];
            }
            FIRST = false;
            continue;
        }
 
        for(int k = 0; k < T; k++){
            table[k][NEXT] = -1;
        }
 
        for(int a = 0; a < T; a++){
            if(table[a][CURRENT] == -1)continue;
            for(int b = 0; b < T; b++){
                if(dp[i][b] == -1)continue;
 
                table[(a+b)%T][NEXT] = max(table[(a+b)%T][NEXT],table[a][CURRENT]+dp[i][b]);
            }
        }
        swap(CURRENT,NEXT);
    }
 
    //右から左に情報を伝える
    for(int i = T-2; i >= 0; i--){
        table[i][CURRENT] = max(table[i+1][CURRENT],table[i][CURRENT]);
    }
 
    int Q;
    scanf("%d",&Q);
 
    ll A,B;
 
    for(int loop = 0; loop < Q; loop++){
        scanf("%lld %lld",&A,&B);
 
        if(table[A][CURRENT] != -1 && table[A][CURRENT]/T >= B){
            printf("yes\n");
        }else{
            printf("no\n");
        }
    }
 
    return 0;
}