Саша har $n$ äpplen med heltalsvikter $w_1,w_2,\ldots,w_n$ som ligger på bordet, samt två rymliga korgar.
Саша väljer ett heltal $k$ och betraktar äpplena som väger högst $k$. Därefter kan hon lägga varje äpple med vikten $w_i\le k$ i en av de två korgarna eller låta det ligga kvar på bordet. Äpplen med vikten $w_i>k$ ligger alltid kvar på bordet.
Vi kallar ett talpar $(x,y)$ för $k$-nåbart om Саша kan lägga några äpplen som väger högst $k$ i korgarna så att summan av äpplenas vikter i den första korgen blir $x$ och summan i den andra korgen blir $y$. Vi kallar ett talpar $(a,b)$ för $k$-idealt om paret $(x,y)$ är $k$-nåbart för alla $x$ och $y$ med $0\le x\le a$ och $0\le y\le b$.
Саша betraktar $q$ tripplar av tal $k,a,b$ och vill för var och en avgöra om paret $(a,b)$ är $k$-idealt.
Indata
Den första raden innehåller två heltal $n$ och $q$: antalet äpplen som Саша har och antalet frågor som du ska behandla ($1\le n,q\le300\,000$).
Den andra raden innehåller $n$ heltal $w_1,w_2,\ldots,w_n$, vikterna på Сашаs äpplen ($1\le w_i\le10^{12}$).
Den tredje raden innehåller heltalet $z$, som används för att skapa frågorna som ska besvaras ($0\le z\le10^6$).
De följande $q$ raderna beskriver frågorna. Frågorna numreras från $1$ till $q$. Varje rad innehåller tre heltal $j,c,d$ ($0\le j,c,d\le10^{18}$). Frågan skapas från talen på raden enligt följande regler. Låt $v$ vara summan av numren på de frågor som ställts före den aktuella frågan och för vilka paret $(a,b)$ i frågan var $k$-idealt. Då gäller för den aktuella frågan $k=j-v\cdot z$, $a=c-v\cdot z$ och $b=d-v\cdot z$. Det garanteras att $k,a,b\ge0$.
Observera att när $z=0$ (vilket gäller för de flesta deluppgifter) är värdena på $k,a,b$ lika med $j,c,d$ respektive. Frågans parametrar beror alltså inte på svaren på tidigare frågor och ges uttryckligen i indata.
Utdata
Skriv Yes för varje fråga om paret $(a,b)$ i frågan är $k$-idealt, och annars No.
Poängsättning
| Deluppgift | Poäng | Ytterligare begränsningar: $n,q$ | Ytterligare begränsningar: $a,b$ | Ytterligare begränsningar: $k$ | Ytterligare begränsningar: $z$ | Nödvändiga deluppgifter |
|---|---|---|---|---|---|---|
| $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\le1\,500$ | $a,b\le1\,500$ | $k=10^{18}$ | $z=0$ | $4$–$5$ |
| $7$ | $6$ | $n\le5\,000$ | $a,b\le5\,000$ | $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\le1\,500$ | $a,b\le1\,500$ | $z=0$ | $4$, $11$ | |
| $14$ | $2$ | $n\le1\,500$ | $a,b\le1\,500$ | $z=0$ | $4$–$6$, $11$–$13$ | |
| $15$ | $6$ | $n\le5\,000$ | $a,b\le5\,000$ | $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$ | Exempel, $1$–$17$ |
Exempel
Indata 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
Utdata 1
Yes No No Yes No
Indata 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
Utdata 2
Yes No No Yes No