Саша tiene $n$ manzanas con pesos enteros $w_1,w_2,\ldots,w_n$ sobre la mesa, así como dos cestas de gran capacidad.
Саша elige un entero $k$ y considera las manzanas cuyo peso no supera $k$. Después puede poner cada manzana de peso $w_i\le k$ en una de las dos cestas o dejarla sobre la mesa. Las manzanas de peso $w_i>k$ permanecen sobre la mesa en cualquier caso.
Llamaremos a un par de números $(x,y)$ alcanzable para $k$ si Саша puede poner algunas manzanas de peso no mayor que $k$ en las cestas de manera que la suma de los pesos de las manzanas de la primera cesta sea $x$ y la de la segunda sea $y$. Llamaremos a un par de números $(a,b)$ ideal para $k$ si, para todos los valores $x$ e $y$ tales que $0\le x\le a$ y $0\le y\le b$, el par $(x,y)$ es alcanzable para $k$.
Саша considera $q$ ternas de números $k,a,b$ y quiere saber, para cada una de ellas, si el par $(a,b)$ es ideal para $k$.
Entrada
La primera línea contiene dos enteros $n$ y $q$: el número de manzanas que tiene Саша y el número de consultas que debes procesar ($1\le n,q\le300\,000$).
La segunda línea contiene $n$ enteros $w_1,w_2,\ldots,w_n$: los pesos de las manzanas de Саша ($1\le w_i\le10^{12}$).
La tercera línea contiene un entero $z$, que se utiliza para construir las consultas que debes responder ($0\le z\le10^6$).
Las siguientes $q$ líneas describen las consultas, numeradas de $1$ a $q$. Cada línea contiene tres enteros $j,c,d$ ($0\le j,c,d\le10^{18}$). La consulta se construye a partir de los números de esta línea según las siguientes reglas. Sea $v$ la suma de los índices de las consultas anteriores a la actual en las que el par $(a,b)$ resultó ser ideal para $k$. Entonces, en la consulta actual, $k=j-v\cdot z$, $a=c-v\cdot z$ y $b=d-v\cdot z$. Se garantiza que $k,a,b\ge0$.
Observa que, cuando $z=0$ (lo que se cumple en la mayoría de las subtareas), los valores de $k,a,b$ son iguales a $j,c,d$, respectivamente. Es decir, los parámetros de la consulta no dependen de las respuestas a las consultas anteriores y se proporcionan explícitamente en la entrada.
Salida
Para cada consulta, imprime Yes si el par $(a,b)$ de esa consulta es ideal para $k$; en caso contrario, imprime No.
Subtareas
| Subtarea | Puntos | Restricciones adicionales: $n,q$ | Restricciones adicionales: $a,b$ | Restricciones adicionales: $k$ | Restricciones adicionales: $z$ | Subtareas necesarias |
|---|---|---|---|---|---|---|
| $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$ | Ejemplos, $1$–$17$ |
Ejemplos
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
Salida 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
Salida 2
Yes No No Yes No