Apples into Baskets

Sasha has $n$ apples with integer weights $w_1, w_2, \ldots, w_n$, lying on a table. She also has two spacious baskets.

Sasha picks an integer $k$ and looks at the apples with weight at most $k$. She may put each apple with $w_i \le k$ into one of the two baskets, or leave it on the table. Apples with $w_i > k$ always stay on the table.

A pair of numbers $(x, y)$ is called $k$-reachable if Sasha can put some apples of weight at most $k$ into the baskets so that the total weight in the first basket is $x$ and the total weight in the second basket is $y$.

A pair $(a, b)$ is called $k$-ideal if for every $x$ and $y$ with $0 \le x \le a$ and $0 \le y \le b$, the pair $(x, y)$ is $k$-reachable.

Sasha has $q$ triples of numbers $k$, $a$, $b$. For each triple she wants to know whether the pair $(a, b)$ is $k$-ideal.

The first line contains two integers $n$ and $q$, the number of apples and the number of queries ($1 \le n, q \le 300\,000$).

The second line contains $n$ integers $w_1, w_2, \dots, w_n$, the weights of the apples ($1 \le w_i \le 10^{12}$).

The third line contains an integer $z$, which is used to build the queries ($0 \le z \le 10^6$).

Each of the next $q$ lines contains three integers $j$, $c$, $d$ ($0 \le j, c, d \le 10^{18}$). Let $v$ be the sum of the numbers of the earlier queries whose pair $(a, b)$ was $k$-ideal. The current query is then $k = j - v \cdot z$, $a = c - v \cdot z$, $b = d - v \cdot z$. It is guaranteed that $k, a, b \ge 0$.

If $z = 0$ (which holds for most subtasks), then $k$, $a$, $b$ equal $j$, $c$, $d$. In that case the query parameters do not depend on earlier answers and are given directly in the input.

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