Sora está acostumbrado a pasar las noches estudiando Programación Competitiva. Como la OCI está cada vez más cerca lleva varias noches seguidas sin dormir mucho, por lo que la noche antes de la competencia terminó durmiéndose en medio de su entrenamiento.

En su sueño, Sora está en una ciudad donde hay ~N~ copas de cristal en el cielo. Las copas están numeradas desde ~1~ hasta ~N~. La resistencia de la copa ~i~ (~1 \le i \le N~) es ~A_i~.

Para poner a prueba a Sora, Sekai atacará el cielo ~Q~ veces. Los ataques estarán numerados desde ~1~ hasta ~Q~. El ataque ~j~ (~1 \le j \le Q~) ejercerá una fuerza positiva ~F_j~ sobre las copas en el rango ~[L_j, R_j]~ (~1\le L_j \le R_j \le N~).

La diferencia entre dos listas ~A~ y ~B~ (~A \setminus B~) es otra lista cuyos elementos son todos los de ~A~ que no lo sean de ~B~; es decir, ~A \setminus B = \{x: x\in A \text{ y } x \notin B\}~.

Cuando Sekai realiza un ataque con una fuerza inicial ~f~ sobre una lista de ~k~ copas ~S=(s_1, s_2, \ldots, s_k)~, ocurrirá lo siguiente:

1. Sea ~C~ la lista de todas las copas de ~S~ con una resistencia menor o igual que ~f~: ~C=\{c\in S : c\le f\}~.
2. Todas las copas que pertenecen a ~C~ caerán al suelo y se romperán, por lo que ~S~ no seguirá conteniendo a esas copas: ~S' = S\setminus C~.
3. Las copas rotas ejercen una nueva fuerza ~f'~ sobre las demás copas; esa fuerza será igual a la suma de cada una de sus resistencias: ~f'=\displaystyle\sum\limits_{c \in C} c~.
4. Si ~f'~ es positiva, volver al paso 1 con ~f = f'~ y ~S = S'~.

Sora restaurará el cielo y las copas caídas cada vez que un ataque termine, pero para ello necesita saber cuántas copas caerán después del ataque. Escribe un programa que para cada uno de los ~Q~ ataques de Sekai compute la cantidad de copas que caerán con ese ataque.

Entrada

La primera línea contiene dos enteros ~N~ y ~Q~ ~-~ la cantidad de copas en el cielo y la cantidad de ataques que realizará Sekai, respectivamente.

La segunda línea contiene ~N~ enteros ~A_1, A_2, \ldots, A_N~ ~-~ la resistencia de la copa ~i~.

Le siguen ~Q~ líneas, la ~j-~ésima de esas líneas contiene tres enteros ~L_j~, ~R_j~ y ~F_j~ ~-~ la descripción del ataque ~j~.

Salida

La salida debe contener ~Q~ líneas ~-~ la cantidad de copas que se cayeron tras cada ataque, en el orden que se realizaron.

Restricciones

• ~1\le N \le 10^5~
• ~1\le Q\le 2\cdot 10^5~
• ~1\le A_i\le 10^9~ para cada ~i~ tal que ~1\le i\le N~
• ~1\le L_j\le R_j\le N~ para cada ~j~ tal que ~1\le j\le Q~
• ~1\le F_j\le 10^9~ para cada ~j~ tal que ~1\le j\le Q~

Subtareas

Subtarea	Restricciones Adicionales	Puntos	Dependencias
~1~	~A_i = A_j~ para cada ~i, j, k~ tal que ~L_k \le i\le j \le R_k~ y ~1 \le k \le Q~	~5~	~-~
~2~	~1\le N\le 5000~; ~1\le Q\le 5000~; ~1\le A_i \le 10~ para cada ~i~ tal que ~1 \le i \le N~; ~1\le F_j \le 10~ para cada ~j~ tal que ~1 \le j \le Q~	~10~	~-~
~3~	La cantidad de elementos diferentes de ~A~ no excede ~10~	~18~	~-~
~4~	~A_{i-1} \le A_{i}~ para cada ~i~ tal que ~2 \le i \le N~	~17~	~-~
~5~	~Q \le 5\cdot 10^4~	~20~	~2~
~6~	~-~	~30~	~1-5~

Ejemplos

Entrada 1

6 4
9 3 2 5 10 2
2 3 2
2 3 3
4 6 9
1 6 2

Salida 1

1
2
2
3

Los ataques de Sekai ocurren de la siguiente manera:

• Ataque ~1~: Se ataca la lista de copas ~S = (3,2)~ con una fuerza inicial ~f = 2~.
  1. En el primer paso se cae la lista de copas ~C = (2)~ lo que provoca una nueva fuerza ~f' = 2~. Por lo que quedaría la lista ~S = (3)~ y ~f = 2~.
  2. La nueva fuerza no es suficiente para hacer caer ninguna de las copas restantes y el ataque termina.

En total cayó ~1~ copa.

• Ataque ~2~: Se ataca la lista de copas ~S=(3,2)~ con fuerza inicial ~f=3~.
  1. En el primer paso se cae la lista de copas ~C = (3,2)~ lo que provoca una nueva fuerza ~f' = 5~. Por lo que quedaría la lista ~S = ()~ y ~f = 5~.
  2. No quedan más copas en la lista ~S~ y el ataque termina.

En total cayeron ~2~ copas.

• Ataque ~3~: Se ataca la lista de copas ~S=(5,10,2)~ con fuerza inicial ~f=9~.
  1. En el primer paso se cae la lista de copas ~C = (5,2)~ lo que provoca una nueva fuerza ~f' = 7~. Por lo que quedaría la lista ~S = (10)~ y ~f = 7~.
  2. La nueva fuerza no es suficiente para hacer caer ninguna de las copas restantes y el ataque termina.

En total cayeron ~2~ copas.

• Ataque ~4~: Se ataca la lista de copas ~S=(9,3,2,5,10,2)~ con fuerza inicial ~f=2~.
  1. En el primer paso se cae la lista de copas ~C = (2,2)~ lo que provoca una nueva fuerza ~f' = 4~. Por lo que quedaría la lista ~S = (9,3,5,10)~ y ~f = 4~.
  2. En el segundo paso se cae la lista de copas ~C = (3)~ lo que provoca una nueva fuerza ~f' = 3~. Por lo que quedaría la lista ~S = (9,5,10)~ y ~f = 3~.
  3. La nueva fuerza no es suficiente para hacer caer ninguna de las copas restantes y el ataque termina.

En total cayeron ~3~ copas.