Саша 有 $n$ 個放在桌上的蘋果，其重量都是整數，分別為 $w_1,w_2,\ldots,w_n$。她還有兩個容量很大的籃子。
Саша 選擇一個整數 $k$，並考慮重量不超過 $k$ 的蘋果。接著，她可以將每個重量為 $w_i\le k$ 的蘋果放進兩個籃子中的一個，或留在桌上。重量為 $w_i>k$ 的蘋果無論如何都留在桌上。
若 Саша 能將一些重量不超過 $k$ 的蘋果放入籃子，使第一個籃子中蘋果的重量總和為 $x$、第二個籃子中蘋果的重量總和為 $y$，則稱數對 $(x,y)$ 為 $k$-可達的。若對所有滿足 $0\le x\le a$ 且 $0\le y\le b$ 的 $x$ 和 $y$，數對 $(x,y)$ 都是 $k$-可達的，則稱數對 $(a,b)$ 為 $k$-理想的。
Саша 考慮 $q$ 組三個數 $k,a,b$，並想對每一組判斷數對 $(a,b)$ 是否為 $k$-理想的。
輸入格式
第一行給出兩個整數 $n$ 和 $q$，分別為 Саша 擁有的蘋果數量和你需要處理的詢問數量（$1\le n,q\le300\,000$）。
第二行給出 $n$ 個整數 $w_1,w_2,\ldots,w_n$，表示 Саша 擁有的蘋果的重量（$1\le w_i\le10^{12}$）。
第三行給出一個整數 $z$，用於產生你需要回答的詢問（$0\le z\le10^6$）。
接下來的 $q$ 行給出詢問的描述。詢問編號為 $1$ 到 $q$。每行包含三個整數 $j,c,d$（$0\le j,c,d\le10^{18}$）。按照以下規則由這一行的數字產生詢問：令 $v$ 為當前詢問之前、數對 $(a,b)$ 是 $k$-理想的那些詢問的編號之和。則當前詢問中 $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