Саша hat $n$ Äpfel mit ganzzahligen Gewichten $w_1,w_2,\ldots,w_n$, die auf dem Tisch liegen, und außerdem zwei geräumige Körbe.
Саша wählt eine ganze Zahl $k$ und betrachtet die Äpfel mit einem Gewicht von höchstens $k$. Anschließend kann sie jeden Apfel mit Gewicht $w_i\le k$ in einen der beiden Körbe legen oder auf dem Tisch lassen. Äpfel mit Gewicht $w_i>k$ bleiben in jedem Fall auf dem Tisch.
Ein Zahlenpaar $(x,y)$ heißt $k$-erreichbar, wenn Саша einige Äpfel mit einem Gewicht von höchstens $k$ so in die Körbe legen kann, dass die Summe der Gewichte der Äpfel im ersten Korb gleich $x$ und die Summe der Gewichte der Äpfel im zweiten Korb gleich $y$ ist. Ein Zahlenpaar $(a,b)$ heißt $k$-ideal, wenn für alle $x$ und $y$ mit $0\le x\le a$ und $0\le y\le b$ das Paar $(x,y)$ $k$-erreichbar ist.
Саша betrachtet $q$ Zahlentripel $k,a,b$ und möchte für jedes davon wissen, ob das Paar $(a,b)$ $k$-ideal ist.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen $n$ und $q$ — die Anzahl der Äpfel, die Саша hat, und die Anzahl der Anfragen, die Sie bearbeiten müssen ($1\le n,q\le300\,000$).
Die zweite Zeile enthält $n$ ganze Zahlen $w_1,w_2,\ldots,w_n$ — die Gewichte der Äpfel, die Саша hat ($1\le w_i\le10^{12}$).
Die dritte Zeile enthält eine ganze Zahl $z$, die zur Bildung der zu beantwortenden Anfragen verwendet wird ($0\le z\le10^6$).
Die folgenden $q$ Zeilen enthalten die Beschreibungen der Anfragen. Die Anfragen sind von $1$ bis $q$ nummeriert. Jede Zeile enthält drei ganze Zahlen $j,c,d$ ($0\le j,c,d\le10^{18}$). Die Anfrage wird aus den Zahlen in dieser Zeile nach den folgenden Regeln gebildet. Berechnen wir $v$ als Summe der Nummern aller Anfragen vor der aktuellen Anfrage, bei denen das in der Anfrage angegebene Paar $(a,b)$ $k$-ideal war. Dann gilt in der aktuellen Anfrage $k=j-v\cdot z$, $a=c-v\cdot z$ und $b=d-v\cdot z$. Es ist garantiert, dass $k,a,b\ge0$.
Beachten Sie, dass für $z=0$ (was für die meisten Teilaufgaben gilt) die Werte $k,a,b$ jeweils gleich $j,c,d$ sind. Die Parameter einer Anfrage hängen dann also nicht von den Antworten auf frühere Anfragen ab und sind in der Eingabe ausdrücklich angegeben.
Ausgabe
Geben Sie für jede Anfrage Yes aus, wenn das Paar $(a,b)$ in dieser Anfrage $k$-ideal ist, und andernfalls No.
Teilaufgaben
| Teilaufgabe | Punkte | Zusätzliche Beschränkungen: $n,q$ | Zusätzliche Beschränkungen: $a,b$ | Zusätzliche Beschränkungen: $k$ | Zusätzliche Beschränkungen: $z$ | Benötigte Teilaufgaben |
|---|---|---|---|---|---|---|
| $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$ | Beispiele, $1$–$17$ |
Beispiele
Eingabe 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
Ausgabe 1
Yes No No Yes No
Eingabe 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
Ausgabe 2
Yes No No Yes No