经验收集

时间限制：1000ms

空间限制：512MB

题目描述

小季正在玩一个游戏，该游戏中有 $n$ 种怪物，每种怪物的数量都是无限的，击败第 $i$ 种怪物可以获得 $a_i$ 点经验值。

现在需要 $m$ 点经验值升到下一级。作为一个强迫症，小季想要恰好获得 $m$ 点经验值，所以小季会尝试击败一些怪物，再把多出来的经验值去购买若干件消耗 $k$ 点经验值的物品。

小季想知道只选取一部分种类的怪物击败，是否可以通过上述操作恰好获得 $m$ 点经验值。

输入描述

第一行输入三个整数 $n$, $m$, $k$，分别代表怪物种数，所需获得经验值和购买物品需要消耗的经验值。

第二行输入 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$，代表击败每种怪物可以获得的经验值。

第三行输入一个整数 $q$，代表询问组数。

接下来 $q$ 行每行两个整数 $l$ 和 $r$，代表选取从第 $l$ 种怪物到第 $r$ 种怪物当中的怪物，进行击败。

输出描述

输出 $q$ 行，对于每一组询问，输出 “YES” 代表该组询问可以恰好获得 $m$ 点经验值，否则输出 “NO”（不包括引号）

样例1

输入

5 10 9
4 6 9 1 8
3
1 5
2 3
1 1

输出

YES
NO
YES

样例1解释

对于第一组询问，允许我们选取所有种类的怪物，一种方式是击败10只第4种怪物，刚好获得10点经验值；

对于第二组询问，无论怎么击杀和购买，都不能刚好获得10点经验值；

对于第三组询问，只能选取第一种怪物击败，可以击败7只怪物，再购买2件物品，获得7 * 4 - 2 * 9 = 28 - 18 = 10点经验值。

数据范围与约定

对于 $10\%$ 的数据，$k = 1$;

对于 $50\%$ 的数据，$1 \le n, q \le 1000$;

对于 $100\%$ 的数据，$1 \le n, q \le 2*10^5$, $1 \le m, k \le 10^9$, $1 \le a_i \le 10^9$, $1 \le l \le r \le n$.

Bonus: 过了本题之后可以思考一下，如果$k=0$，能不能进行求解。