Саша ha $n$ mele di pesi interi $w_1,w_2,\ldots,w_n$, che si trovano sul tavolo, e due cesti capienti.
Саша sceglie un intero $k$ e considera le mele di peso non superiore a $k$. Può quindi mettere ogni mela di peso $w_i\le k$ in uno dei due cesti oppure lasciarla sul tavolo. Le mele di peso $w_i>k$ rimangono sul tavolo in ogni caso.
Chiamiamo una coppia di numeri $(x,y)$ raggiungibile con $k$ se Саша può mettere nei cesti alcune mele di peso non superiore a $k$ in modo che la somma dei pesi delle mele nel primo cesto sia $x$ e la somma dei pesi delle mele nel secondo cesto sia $y$. Chiamiamo una coppia di numeri $(a,b)$ ideale con $k$ se, per tutti gli $x$ e $y$ tali che $0\le x\le a$ e $0\le y\le b$, la coppia $(x,y)$ è raggiungibile con $k$.
Саша considera $q$ terne di numeri $k,a,b$ e, per ognuna, vuole sapere se la coppia $(a,b)$ è ideale con $k$.
Input
La prima riga contiene due interi $n$ e $q$: il numero di mele che Саша possiede e il numero di richieste da elaborare ($1\le n,q\le300\,000$).
La seconda riga contiene $n$ interi $w_1,w_2,\ldots,w_n$: i pesi delle mele che Саша possiede ($1\le w_i\le10^{12}$).
La terza riga contiene un intero $z$, utilizzato per costruire le richieste a cui bisogna rispondere ($0\le z\le10^6$).
Le successive $q$ righe descrivono le richieste, numerate da $1$ a $q$. Ogni riga contiene tre interi $j,c,d$ ($0\le j,c,d\le10^{18}$). La richiesta si costruisce dai numeri di questa riga secondo le seguenti regole. Calcoliamo $v$ come la somma dei numeri delle richieste precedenti a quella corrente per le quali la coppia $(a,b)$ indicata nella richiesta era ideale con $k$. Nella richiesta corrente si ha quindi $k=j-v\cdot z$, $a=c-v\cdot z$, $b=d-v\cdot z$. È garantito che $k,a,b\ge0$.
Si noti che, quando $z=0$ (come nella maggior parte delle sottoprove), i valori $k,a,b$ sono uguali rispettivamente a $j,c,d$. Quindi i parametri della richiesta non dipendono dalle risposte alle richieste precedenti e sono forniti esplicitamente nell'input.
Output
Per ogni richiesta, stampa Yes se la coppia $(a,b)$ di quella richiesta è ideale con $k$, altrimenti stampa No.
Sottoprove
| Sottoprova | Punti | Vincoli aggiuntivi: $n,q$ | Vincoli aggiuntivi: $a,b$ | Vincoli aggiuntivi: $k$ | Vincoli aggiuntivi: $z$ | Sottoprove necessarie |
|---|---|---|---|---|---|---|
| $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\text{–}5$ |
| $7$ | $6$ | $n\le5\,000$ | $a,b\le5\,000$ | $k=10^{18}$ | $z=0$ | $4\text{–}6$ |
| $8$ | $2$ | $a,b\le200\,000$ | $k=10^{18}$ | $z=0$ | $2,4\text{–}7$ | |
| $9$ | $9$ | $k=10^{18}$ | $z=0$ | $2\text{–}8$ | ||
| $10$ | $3$ | $b=0$ | $z=0$ | $2\text{–}3$ | ||
| $11$ | $6$ | $n,q\le100$ | $a,b\le300$ | $z=0$ | $4$ | |
| $12$ | $6$ | $n\le100$ | $a,b\le300$ | $z=0$ | $4\text{–}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\text{–}6,11\text{–}13$ | |
| $15$ | $6$ | $n\le5\,000$ | $a,b\le5\,000$ | $z=0$ | $4\text{–}7,11\text{–}14$ | |
| $16$ | $2$ | $a,b\le200\,000$ | $z=0$ | $4\text{–}8,11\text{–}15$ | ||
| $17$ | $6$ | $z=0$ | $1\text{–}16$ | |||
| $18$ | $18$ | Esempi, $1\text{–}17$ |
Esempi
Input 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
Output 1
Yes No No Yes No
Input 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
Output 2
Yes No No Yes No