Daniyar, el erizo, quiere aprender nuevos algoritmos. Zhanadil, el invisible, quiere ayudar a su amigo, por eso le da a Daniyar ~N~ libros de algoritmos, cada libro tiene un cierto peso ~w_i~ (~1 \le i \le N~). Daniyar organizó los libros de ~1~ a ~N~ en su estante.

El viaje de aprendizaje de Daniyar está distribuido a lo largo de ~M~ días: durante el día ~i~, le interesa leer los libros desde ~l_i~ hasta ~r_i~.

Como perfeccionista, él primero intenta reordenar los libros desde ~l_i~ hasta ~r_i~ en orden no decreciente según sus pesos. Para lograr esto, el erizo puede cambiar de posición dos libros adyacentes dentro del rango ~[l_i, r_i]~ siempre y cuando su peso total no exceda su estado de ánimo ~k_i~. Por suerte, él ya conoce su estado de ánimo en los próximos ~M~ días. Al final de cada día, devuelve los libros a su posición original.

Ayude al erizo a mejorar su plan, calcule la cantidad de días donde su estado de ánimo es suficiente para ordenar los libros en orden no decreciente según sus pesos.

Por ejemplo, asuma que Daniyar está planeando leer ~3~ libros, actualmente ordenados como ~[3, 5, 4]~ y su estado de ánimo es ~8~. Entonces, tristemente, no es posible ya que no puede cambiar de posición los libros con peso 5 y 4 (porque ~8 \le 5 + 4~). Pero si su ánimo fuera ~9~, entonces sería posible ordenar los libros en orden no decreciente según el peso.

Note que cada día es independiente de los demás días, dígase, cada día los libros empiezan en el estado original.

Subtareas

• Subtarea 1 (8 puntos): ~1 \leq N, M \leq 500~.
• Subtarea 2 (9 puntos): ~1 \leq N, M \leq 5000~.
• Subtarea 3 (13 puntos): ~1 \leq N, M \leq 10^6~, ~k=0~.
• Subtarea 4 (17 puntos): ~1 \leq N, M \leq 10^5~, ~0 \leq w_i \leq 1000~.
• Subtarea 5 (30 puntos): ~1 \leq N, M \leq 2*10^5~.
• Subtarea 6 (23 puntos): Sin restricciones adicionales.

Entrada

La primera línea de entrada contiene ~2~ enteros, ~N , M (1 \leq N, M \leq 10^6)~: el número de libros de algoritmos y el número de días.

La segunda línea de entrada contiene ~N~ enteros ~w_1, w_2, ..., w_N~ (~0 \leq w_i \leq 10^9~ para todo ~1 \leq i \leq N~ ) separados por un solo espacio: el peso de cada libro.

Las siguientes ~M~ líneas contienen 3 enteros ~l_i~, ~r_i~, y ~k_i~ (~1 \leq l_i \leq r_i \le N~ y ~0 \le k_i \le 2*10^9~): Daniyar planea leer los libros desde ~l_i~ hasta ~r_i~ con ánimo ~k_i~ en el día ~i~.

Salida

Imprima ~M~ líneas, cada una con un solo dígito. La línea ~i~ deberá contener 1 si es posible que Daniyar lea los libros en el día ~i~, y 0 si no.

Ejemplos

Entrada 1

5 2
3 5 1 8 2
1 3 6
2 5 3

Salida 1

1
0

En la primera pregunta, Daniyar, el erizo, puede lograr el orden correcto de la siguiente forma: ~[3, 5, 1, 8, 2] \to [3, 1, 5, 8, 2] \to [1, 3, 5, 8, 2]~