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:
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
double dot(complex<double> a, complex<double> b) {
	return a.real() * b.real() + a.imag() * b.imag();
}
double gyaku_dot(complex<double> a, complex<double> b) {
	return a.real() * b.imag() - a.imag() * b.real();
}
double leng(complex<double> a) {
	return sqrt(a.real()*a.real() + a.imag()*a.imag());
}
double angles(complex<double> a, complex<double> b) {
	double cosine = dot(a, b) / (leng(a) * leng(b));
	double sine = gyaku_dot(a, b) / (leng(a) * leng(b));
	double kaku = acos(cosine);
	if (sine <= 0) {
		kaku = 2 * Ma_PI - kaku;
	}
	return kaku;
}
vector<int> convex_hull(vector<complex<double>> a) {
	vector<int> ans;
	double now_minnest = a[0].real();
	int now_itr = 0;
	REP(i, a.size()) {
		if (now_minnest > a[i].real()) {
			now_minnest = a[i].real();
			now_itr = i;
		}
	}
	ans.push_back(now_itr);
	complex<double> ba(0, 1);
	while (true) {
		int now_go = 0;
		double now_min = 0;
		int starter = ans[ans.size() - 1];
		for (int i = 0; i < a.size();++i) {
			if (i != starter) {
				double goa = angles(ba, a[i] - a[starter]);
				if (goa > now_min) {
					now_min = goa;
					now_go = i;
				}
			}
		}
		if (now_go == ans[0]) break;
		ans.push_back(now_go);
		ba = complex<double>(a[now_go] - a[starter]);
	}
	return ans;
}
long long dp[20][2000] = {};
long long aa[2000] = {};
int main() {
	long long n, m, t;
	cin >> n >> m >> t;
	REP(i, t) {
		aa[i] = -LONG_INF;
	}
	aa[0] = 0;
	REP(i, 20) {
		REP(q, 2000) {
			dp[i][q] = -LONG_INF;
		}
	}
	dp[0][0] = 0;
	REP(i, n) {
		long long a;
		cin >> a;
		dp[0][a%t] = max(dp[0][a%t], a / t);
		if (m % 2 == 1) {
			aa[a%t] = dp[0][a%t];
		}
	}
	m /= 2;
	int next_itr = 1;
	while (m != 0) {
		for (int i = 0; i < t; ++i) {
			for (int q = 0; q < t; ++q) {
				dp[next_itr][(i + q) % t] = max(dp[next_itr][(i + q) % t], dp[next_itr - 1][q] + dp[next_itr - 1][i] + (i+q)/t);
			}
		}
		if (m % 2 == 1) {
			long long geko[2000] = {};
			REP(i, 2000) {
				geko[i] = aa[i];
			}
			for (int i = 0; i < t; ++i) {
				for (int q = 0; q < t; ++q) {
					geko[(i + q) % t] = max(geko[(i + q) % t], aa[i] + dp[next_itr][q] + (i+q)/t);
				}
			}
			for (int i = 0; i < t; ++i) {
				aa[i] = geko[i];
			}
		}
		m /= 2;
		next_itr++;
	}
	for(int i = t-2;i >= 0;--i){
		aa[i] = max(aa[i + 1], aa[i]);
	}
	int query;
	cin >> query;
	REP(i, query) {
		long long a, b;
		cin >> a >> b;
		if (aa[a] >= b) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}
	return 0;
}