Background

Translated from ROI 2023 D2T3。

Tao Tao has $n$ apples with integer weights $w_1,w_2,\dots,w_n$. They are placed on a table, and there are also two baskets with large enough capacity.

Tao Tao chooses an integer $k$. For each apple with weight $w_i \le k$, he may put it into one of the baskets, or leave it on the table. Apples with weight greater than $k$ will always remain on the table.

If Tao Tao can place the apples of weight at most $k$ into the baskets so that the total weight of apples in the first basket equals $x$, and the total weight of apples in the second basket equals $y$, then $(x, y)$ is called a reachable pair for $k$. If for all $x$ and $y$ satisfying $0 \le x \le a$ and $0 \le y \le b$, $(x, y)$ is a reachable pair for $k$, then $(a, b)$ is called $k-\!$ perfect.

Problem Description

Tao Tao will ask you $q$ times. For each triple $(k,a,b)$, determine whether $(a, b)$ is $k-\!$ perfect.

Input Format

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

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

The third line contains an integer $z$, which will be used in the following input ($0 \le z \le 10^6$).

The next $q$ lines describe the queries. Queries are numbered from $1$ to $q$. Each line contains three integers $j,c,d$ ($0 \le j, c, d \le 10^{18}$), meaning that in this query $k = j - v \times z,a = c - v \times z,b = d - v \times z$, where $v$ is the sum of the indices of the previous queries whose answers were Yes. It is guaranteed that $k,a,b \ge 0$.

In this problem, for most testdata, $z$ equals $0$. In this case, the values of $k,a,b$ are $j,c,d$, respectively.

Output Format

For each query, if the pair $(a, b)$ is $k-\!$ perfect in that query, output Yes; otherwise output No.

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

Yes
No
No
Yes
No

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

Yes
No
No
Yes
No

Hint

Translated by ChatGPT 5