Саша tem $n$ maçãs com pesos inteiros $w_1,w_2,\ldots,w_n$, que estão sobre a mesa, e dois cestos espaçosos.
Саша escolhe um inteiro $k$ e considera as maçãs cujo peso não excede $k$. Em seguida, pode colocar cada maçã de peso $w_i\le k$ num dos dois cestos ou deixá-la sobre a mesa. As maçãs de peso $w_i>k$ permanecem sempre sobre a mesa.
Chamaremos um par de números $(x,y)$ de alcançável para $k$ se Саша puder colocar algumas maçãs de peso não superior a $k$ nos cestos de modo que a soma dos pesos das maçãs no primeiro cesto seja $x$ e a soma dos pesos das maçãs no segundo cesto seja $y$. Chamaremos um par de números $(a,b)$ de ideal para $k$ se, para todos os $x$ e $y$ tais que $0\le x\le a$ e $0\le y\le b$, o par $(x,y)$ for alcançável para $k$.
Саша considera $q$ triplos de números $k,a,b$ e, para cada um, quer saber se o par $(a,b)$ é ideal para $k$.
Entrada
A primeira linha contém dois inteiros $n$ e $q$: o número de maçãs de Саша e o número de consultas que deve processar ($1\le n,q\le300\,000$).
A segunda linha contém $n$ inteiros $w_1,w_2,\ldots,w_n$: os pesos das maçãs de Саша ($1\le w_i\le10^{12}$).
A terceira linha contém um inteiro $z$, usado para construir as consultas às quais é necessário responder ($0\le z\le10^6$).
As próximas $q$ linhas descrevem as consultas. As consultas são numeradas de $1$ a $q$. Cada linha contém três inteiros $j,c,d$ ($0\le j,c,d\le10^{18}$). A consulta é construída a partir dos números dessa linha segundo as regras seguintes. Calcule $v$ como a soma dos índices das consultas anteriores à atual para as quais o par $(a,b)$ indicado na consulta era ideal para $k$. Então, na consulta atual, $k=j-v\cdot z$; $a=c-v\cdot z$; $b=d-v\cdot z$. É garantido que $k,a,b\ge0$.
Observe que, quando $z=0$ (o que acontece na maioria das subtarefas), os valores $k,a,b$ são iguais a $j,c,d$, respetivamente. Ou seja, os parâmetros da consulta não dependem das respostas às consultas anteriores e são fornecidos explicitamente na entrada.
Saída
Para cada consulta, imprima Yes se o par $(a,b)$ dessa consulta for ideal para $k$; caso contrário, imprima No.
Subtarefas
| Subtarefa | Pontos | Restrições adicionais: $n,q$ | Restrições adicionais: $a,b$ | Restrições adicionais: $k$ | Restrições adicionais: $z$ | Subtarefas necessárias |
|---|---|---|---|---|---|---|
| $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$ | Exemplos, $1$–$17$ |
Exemplos
Entrada 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
Saída 1
Yes No No Yes No
Entrada 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
Saída 2
Yes No No Yes No