Sasha 有 $n$ 个苹果，它们的重量分别为整数 $w_1, w_2, \dots, w_n$，这些苹果都放在桌子上。此外，她还有两个容量很大的篮子。
Sasha 选择一个整数 $k$，并考虑所有重量不超过 $k$ 的苹果。之后，她可以将每个重量 $w_i \leqslant k$ 的苹果放入两个篮子中的任意一个，或者将其留在桌子上。重量 $w_i > k$ 的苹果无论如何都会留在桌子上。
如果 Sasha 可以将一些重量不超过 $k$ 的苹果放入篮子，使得第一个篮子中苹果的总重量为 $x$，第二个篮子中苹果的总重量为 $y$，则称数对 $(x, y)$ 是 $k$-可达的。如果对于所有满足 $0 \leqslant x \leqslant a$ 且 $0 \leqslant y \leqslant b$ 的 $x$ 和 $y$，数对 $(x, y)$ 都是 $k$-可达的，则称数对 $(a, b)$ 是 $k$-理想的。
Sasha 考虑了 $q$ 个三元组 $(k, a, b)$，并希望对每一个三元组判断数对 $(a, b)$ 是否为 $k$-理想的。
输入格式
第一行包含两个整数 $n$ 和 $q$ —— Sasha 拥有的苹果数量以及你需要处理的查询数量 ($1 \leqslant n, q \leqslant 300\,000$)。
第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ —— Sasha 拥有的苹果重量 ($1 \leqslant w_i \leqslant 10^{12}$)。
第三行包含一个整数 $z$，用于生成查询 ($0 \leqslant z \leqslant 10^6$)。
接下来的 $q$ 行包含查询描述。查询编号从 $1$ 到 $q$。每行包含三个整数 $j, c$ 和 $d$ ($0 \leqslant j, c, d \leqslant 10^{18}$)。查询参数根据以下规则生成：设 $v$ 为当前查询之前所有被判定为 $k$-理想的查询的编号之和。那么在当前查询中，$k = j - v \cdot z$；$a = c - v \cdot z$；$b = d - v \cdot z$。保证 $k, a, b \geqslant 0$。
注意，当 $z = 0$ 时（大多数子任务的情况），$k, a, b$ 的值分别等于 $j, c, d$。也就是说，查询参数不依赖于之前查询的结果，并以显式形式给出。
输出格式
对于每个查询，如果该查询中的数对 $(a, b)$ 是 $k$-理想的，则输出 “Yes”，否则输出 “No”。
子任务
| 子任务 | 分值 | $n, q$ | $a, b$ | $k$ | $z$ | 依赖子任务 |
|---|---|---|---|---|---|---|
| 1 | 9 | $n, q \leqslant 10$ | $z = 0$ | |||
| 2 | 6 | $n \leqslant 100$ | $a \leqslant 100\,000, b = 0$ | $k = 10^{18}$ | $z = 0$ | |
| 3 | 3 | $b = 0$ | $k = 10^{18}$ | $z = 0$ | 2 | |
| 4 | 6 | $n, q \leqslant 100$ | $a, b \leqslant 300$ | $k = 10^{18}$ | $z = 0$ | |
| 5 | 6 | $n \leqslant 100$ | $a, b \leqslant 300$ | $k = 10^{18}$ | $z = 0$ | 4 |
| 6 | 2 | $n \leqslant 1\,500$ | $a, b \leqslant 1\,500$ | $k = 10^{18}$ | $z = 0$ | 4–5 |
| 7 | 6 | $n \leqslant 5\,000$ | $a, b \leqslant 5\,000$ | $k = 10^{18}$ | $z = 0$ | 4–6 |
| 8 | 2 | $a, b \leqslant 200\,000$ | $k = 10^{18}$ | $z = 0$ | 2, 4–7 | |
| 9 | 9 | $k = 10^{18}$ | $z = 0$ | 2–8 | ||
| 10 | 3 | $b = 0$ | $z = 0$ | 2–3 | ||
| 11 | 6 | $n, q \leqslant 100$ | $a, b \leqslant 300$ | $z = 0$ | 4 | |
| 12 | 6 | $n \leqslant 100$ | $a, b \leqslant 300$ | $z = 0$ | 4–5, 11 | |
| 13 | 2 | $n, q \leqslant 1\,500$ | $a, b \leqslant 1\,500$ | $z = 0$ | 4, 11 | |
| 14 | 2 | $n \leqslant 1\,500$ | $a, b \leqslant 1\,500$ | $z = 0$ | 4–6, 11–13 | |
| 15 | 6 | $n \leqslant 5\,000$ | $a, b \leqslant 5\,000$ | $z = 0$ | 4–7, 11–14 | |
| 16 | 2 | $a, b \leqslant 200\,000$ | $z = 0$ | 4–8, 11–15 | ||
| 17 | 6 | $z = 0$ | 1–16 | |||
| 18 | 18 | 1–17 |
样例
输入 1
8 5 17 1 3 2 100 5 6 1 0 6 15 3 9 4 4 5 15 3 17 34 1 16 33 2
输出 1
Yes No No Yes No
输入 2
8 5 17 1 3 2 100 5 6 1 1 6 15 3 10 5 5 6 16 4 18 35 2 21 38 7
输出 2
Yes No No Yes No