Саша possède $n$ pommes de poids entiers $w_1,w_2,\ldots,w_n$, posées sur une table, ainsi que deux grands paniers.
Саша choisit un entier $k$ et considère les pommes dont le poids ne dépasse pas $k$. Elle peut ensuite placer chaque pomme de poids $w_i\le k$ dans l'un des deux paniers, ou la laisser sur la table. Les pommes de poids $w_i>k$ restent dans tous les cas sur la table.
On dit qu'une paire de nombres $(x,y)$ est $k$-atteignable si Саша peut placer certaines pommes de poids au plus $k$ dans les paniers de sorte que la somme des poids des pommes du premier panier soit égale à $x$ et celle des pommes du second panier à $y$. On dit qu'une paire de nombres $(a,b)$ est $k$-idéale si, pour tous les $x$ et $y$ tels que $0\le x\le a$ et $0\le y\le b$, la paire $(x,y)$ est $k$-atteignable.
Саша considère $q$ triplets de nombres $k,a,b$ et souhaite savoir, pour chacun d'eux, si la paire $(a,b)$ est $k$-idéale.
Entrée
La première ligne contient deux entiers $n$ et $q$ : le nombre de pommes que possède Саша et le nombre de requêtes à traiter ($1\le n,q\le300\,000$).
La deuxième ligne contient $n$ entiers $w_1,w_2,\ldots,w_n$ : les poids des pommes que possède Саша ($1\le w_i\le10^{12}$).
La troisième ligne contient un entier $z$, utilisé pour construire les requêtes auxquelles il faut répondre ($0\le z\le10^6$).
Les $q$ lignes suivantes décrivent les requêtes. Les requêtes sont numérotées de $1$ à $q$. Chaque ligne contient trois entiers $j,c,d$ ($0\le j,c,d\le10^{18}$). La requête est construite à partir des nombres de cette ligne selon les règles suivantes. On calcule $v$, la somme des numéros des requêtes précédant la requête actuelle pour lesquelles la paire $(a,b)$ donnée dans la requête était $k$-idéale. Pour la requête actuelle, on a alors $k=j-v\cdot z$, $a=c-v\cdot z$, $b=d-v\cdot z$. Il est garanti que $k,a,b\ge0$.
Remarquez que lorsque $z=0$ (ce qui est le cas dans la plupart des sous-tâches), les valeurs de $k,a,b$ sont respectivement égales à $j,c,d$. Autrement dit, les paramètres d'une requête ne dépendent pas des réponses aux requêtes précédentes et sont donnés explicitement dans l'entrée.
Sortie
Pour chaque requête, affichez Yes si la paire $(a,b)$ de cette requête est $k$-idéale, et No sinon.
Sous-tâches
| Sous-tâche | Points | Contraintes supplémentaires : $n,q$ | Contraintes supplémentaires : $a,b$ | Contraintes supplémentaires : $k$ | Contraintes supplémentaires : $z$ | Sous-tâches requises |
|---|---|---|---|---|---|---|
| $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$ | Exemples, $1$–$17$ |
Exemples
Entrée 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
Sortie 1
Yes No No Yes No
Entrée 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
Sortie 2
Yes No No Yes No