# ROI 23 Apples Into Baskets

https://www.acmicpc.net/problem/28502

Sasha has $n$ apples with integer weights $w_1, w_2, \ldots, w_n$ on a table, as well as two large baskets.

Sasha chooses an integer $k$ and considers apples with a weight no greater than $k$. After this, she can place each apple with weight $w_i \le 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.

We call a pair of numbers $(x, y)$ $k$-achievable if Sasha can place some apples with weight no greater than $k$ into the baskets such that the sum of the weights of the apples in the first basket equals $x$, and the sum of the weights of the apples in the second basket equals $y$. We call a pair of numbers $(a, b)$ $k$-ideal if for all $x$ and $y$ where $0 \le x \le a$ and $0 \le y \le b$, the pair $(x, y)$ is $k$-achievable.

Sasha considers $q$ triples of numbers $(k, a, b)$ and wants to determine for each of them whether the pair $(a, b)$ is $k$-ideal.

## Input

In the first line, there are two integers $n$ and $q$ -- the number of apples Sasha has and the number of queries you need to process $(1 \le n, q \le 300,000)$.

In the second line, there are $n$ integers $w_1$, $w_2$, $\dots$, $w_n$ -- the weights of the apples Sasha has $(1 \le w_i \le 10^{12})$.

In the third line, there is an integer $z$.

In the following $q$ lines, the descriptions of the queries are given. The queries are numbered from $1$ to $q$. Each line contains three integers $j$, $c$, and $d$ $(0 \le j, c, d \le 10^{18})$. The query is formed from the numbers in this line according to the following rules. We calculate $v$ as the sum of the numbers of the queries made before the current one, for which the pair $(a, b)$ specified in the query 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 \geq 0$.

Note that when $z = 0$ (which is true for most subproblems), the values of $k$, $a$, and $b$ are equal to $j$, $c$, and $d$ respectively. That is, the parameters of the query do not depend on the answers to the previous queries and are given explicitly in the input data.

## Output

For each query, print "Yes" if the pair $(a, b)$ in the given query is $k$-ideal, otherwise print "No".

## Scoring and Subtasks


## Sample

### Sample 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

### Sample Output 1

Yes
No
No
Yes
No

### Sample 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

### Sample Output 2

Yes
No
No
Yes
No

This is actually the same testcase as the above, except that $z \neq 0$ which means the input is "encrypted".