Sasha has $n$ apples with integer weights $w_1, w_2, \dots, w_n$ lying on a table, as well as two spacious baskets.
Sasha chooses an integer $k$ and considers apples with weight at most $k$. After that, she can place each apple with weight $w_i \leqslant k$ into one of the two baskets, or leave it on the table. Apples with weight $w_i > k$ remain on the table in any case.
A pair of numbers $(x, y)$ is called $k$-reachable if Sasha can place some apples with weight at most $k$ into the baskets such that the sum of weights of the apples in the first basket is $x$, and the sum of weights of the apples in the second basket is $y$. A pair of numbers $(a, b)$ is called $k$-ideal if for all $x$ and $y$ where $0 \leqslant x \leqslant a$ and $0 \leqslant y \leqslant b$, the pair $(x, y)$ is $k$-reachable.
Sasha considers $q$ triples of numbers $k, a, b$ and for each of them wants to determine whether the pair $(a, b)$ is $k$-ideal.
Input
The first line contains two integers $n$ and $q$ — the number of apples Sasha has and the number of queries you need to process ($1 \leqslant n, q \leqslant 300\,000$).
The second line contains $n$ integers $w_1, w_2, \dots, w_n$ — the weights of the apples Sasha has ($1 \leqslant w_i \leqslant 10^{12}$).
The third line contains an integer $z$, which is used to form the queries that need to be answered ($0 \leqslant z \leqslant 10^6$).
The next $q$ lines contain the descriptions of the queries. The queries are numbered from $1$ to $q$. Each line contains three integers $j, c,$ and $d$ ($0 \leqslant j, c, d \leqslant 10^{18}$). The query is formed from the numbers in this line according to the following rules. Let $v$ be the sum of the indices of the queries made so far for which the given pair $(a, b)$ turned out to be $k$-ideal. Then, in the current query, $k = j - v \cdot z$; $a = c - v \cdot z$; $b = d - v \cdot z$. It is guaranteed that $k, a, b \geqslant 0$.
Note that when $z = 0$ (which is true for most subtasks), the values of $k, a,$ and $b$ are equal to $j, c,$ and $d$ respectively. That is, the query parameters do not depend on the answers to previous queries and are given in the input explicitly.
Output
For each query, output "Yes" if the pair $(a, b)$ in the given query is $k$-ideal, otherwise output "No".
Subtasks
| Subtask | Points | Additional Constraints | Required Subtasks |
|---|---|---|---|
| 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 |
Examples
Input 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
Output 1
Yes No No Yes No
Input 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
Output 2
Yes No No Yes No