Саша は、整数の重さ $w_1,w_2,\ldots,w_n$ を持つ $n$ 個のリンゴを机の上に置いており、さらに十分な容量のあるかごを 2 つ持っています。
Саша は整数 $k$ を選び、重さが $k$ 以下のリンゴを考えます。その後、重さ $w_i\le k$ の各リンゴを 2 つのかごのいずれかに入れるか、机の上に残すことができます。重さ $w_i>k$ のリンゴは、いずれの場合も机の上に残します。
Саша が重さ $k$ 以下のリンゴの一部をかごに入れ、1 つ目のかごのリンゴの重さの合計を $x$、2 つ目のかごのリンゴの重さの合計を $y$ にできるとき、数の組 $(x,y)$ を $k$-到達可能と呼びます。$0\le x\le a$ および $0\le y\le b$ を満たすすべての $x,y$ について、組 $(x,y)$ が $k$-到達可能であるとき、数の組 $(a,b)$ を $k$-理想的と呼びます。
Саша は $q$ 個の 3 つ組 $k,a,b$ を考え、それぞれについて組 $(a,b)$ が $k$-理想的かどうかを知りたいと思っています。
入力
1 行目には 2 つの整数 $n,q$ が与えられます。これらは Саша が持つリンゴの個数と、処理すべきクエリの個数です ($1\le n,q\le300\,000$)。
2 行目には $n$ 個の整数 $w_1,w_2,\ldots,w_n$ が与えられます。これらは Саша が持つリンゴの重さです ($1\le w_i\le10^{12}$)。
3 行目には整数 $z$ が与えられます。これは回答すべきクエリを生成するために使われます ($0\le z\le10^6$)。
続く $q$ 行にはクエリの記述が与えられます。クエリには $1$ から $q$ までの番号が付けられています。各行には 3 つの整数 $j,c,d$ が含まれます ($0\le j,c,d\le10^{18}$)。その行の数から、次の規則でクエリを生成します。現在のクエリより前のクエリのうち、指定された組 $(a,b)$ が $k$-理想的だったクエリの番号の合計を $v$ とします。このとき、現在のクエリでは $k=j-v\cdot z$、$a=c-v\cdot z$、$b=d-v\cdot z$ です。$k,a,b\ge0$ が保証されます。
$z=0$ のとき（ほとんどの小課題がこれに該当します）、$k,a,b$ の値はそれぞれ $j,c,d$ と等しいことに注意してください。つまり、クエリのパラメータはそれまでのクエリの答えに依存せず、入力に明示的に与えられています。
出力
各クエリについて、そのクエリの組 $(a,b)$ が $k$-理想的なら Yes、そうでなければ No を出力してください。
小課題
| 小課題 | 点数 | 追加の制約：$n,q$ | 追加の制約：$a,b$ | 追加の制約：$k$ | 追加の制約：$z$ | 必要な小課題 |
|---|---|---|---|---|---|---|
| $1$ | $9$ | $n,q\le10$ | $z=0$ | |||
| $2$ | $6$ | $n\le100$ | $a\le100\,000$, $b=0$ | $k=10^{18}$ | $z=0$ | |
| $3$ | $3$ | $b=0$ | $k=10^{18}$ | $z=0$ | $2$ | |
| $4$ | $6$ | $n,q\le100$ | $a,b\le300$ | $k=10^{18}$ | $z=0$ | |
| $5$ | $6$ | $n\le100$ | $a,b\le300$ | $k=10^{18}$ | $z=0$ | $4$ |
| $6$ | $2$ | $n\le1500$ | $a,b\le1500$ | $k=10^{18}$ | $z=0$ | $4$–$5$ |
| $7$ | $6$ | $n\le5000$ | $a,b\le5000$ | $k=10^{18}$ | $z=0$ | $4$–$6$ |
| $8$ | $2$ | $a,b\le200\,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\le100$ | $a,b\le300$ | $z=0$ | $4$ | |
| $12$ | $6$ | $n\le100$ | $a,b\le300$ | $z=0$ | $4$–$5$, $11$ | |
| $13$ | $2$ | $n,q\le1500$ | $a,b\le1500$ | $z=0$ | $4$, $11$ | |
| $14$ | $2$ | $n\le1500$ | $a,b\le1500$ | $z=0$ | $4$–$6$, $11$–$13$ | |
| $15$ | $6$ | $n\le5000$ | $a,b\le5000$ | $z=0$ | $4$–$7$, $11$–$14$ | |
| $16$ | $2$ | $a,b\le200\,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