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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
vector<int>atu;
int scan(void){int h,m;cin>>h>>m;atu.pub(h*60+m);return h*60+m;}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,T,h,i,j;cin>>n>>m>>T;
	llint balls[17][1000];//合計
	for(h=0;h<=16;h++){
		for(i=0;i<T;i++){balls[h][i]=-big;}
	}
	balls[0][0]=0;
	for(i=0;i<n;i++){
		llint a;cin>>a;
		maxeq(balls[0][a%T],a);
	}
	for(h=1;h<=16;h++){
		for(i=0;i<T;i++){
			for(j=0;j<T;j++){
				maxeq(balls[h][(i+j)%T],balls[h-1][i]+balls[h-1][j]);
			}
		}
		//for(i=0;i<T;i++){cerr<<balls[h][i]<<" ";}cerr<<endl;
	}
	llint kei[1000];
	for(i=0;i<T;i++){kei[i]=-mod;}
	kei[0]=0;
	for(h=0;h<=16;h++){
		if(!(m&(1<<h))){continue;}
		llint ata[1000];
		for(i=0;i<T;i++){ata[i]=-mod;}
		for(i=0;i<T;i++){
			for(j=0;j<T;j++){
				maxeq(ata[(i+j)%T],kei[i]+balls[h][j]);
			}
		}
		swap(ata,kei);
	}
	for(i=T-1;i>0;i--){maxeq(kei[i-1],kei[i]-1);}
	
	int Q;cin>>Q;
	while(Q--){
		llint A,B;cin>>A>>B;
		cout<<(kei[A]>=(B*T+A)?"yes":"no")<<endl;
	}
	return 0;
}