En la ceremonia de apertura de IOI 2018, $N$ participantes desfilan en fila sobre una recta numérica. Todos avanzan en el sentido positivo de la recta. En el instante $0$, el participante $i$ ($1 \le i \le N$, contando desde la cabeza de la fila) se encuentra en la coordenada $-i$. Además, IOI-chan, que lleva la bandera, se encuentra en la coordenada $0$.

Cada participante tiene un valor llamado lentitud. La lentitud del participante $i$ es $D_i$. Los participantes siguen esta regla:

• Si el participante $i$ se encuentra a una distancia mayor o igual que $D_i+1$ de la persona que tiene justo delante, ya sea otro participante o IOI-chan, se desplaza hasta la posición situada a distancia $1$ de esa persona. En caso contrario, no se mueve.

IOI-chan avanza una distancia de $1$ en el sentido positivo de la recta por unidad de tiempo. Cada participante se mueve instantáneamente en cuanto se cumple la condición anterior.

Eres un periodista que cubre la ceremonia de apertura. Tenías que hacer fotos, pero te quedaste profundamente dormido durante toda la ceremonia. Sin otra solución, has decidido hacer trampa: fotografiarás el recinto y después dibujarás a las personas sobre las fotos.

Para que no descubran el engaño, o para estimar el tiempo necesario para dibujar, quieres conocer los siguientes $Q$ valores:

• El número de personas cuyas coordenadas están entre $L_j$ y $R_j$, ambos incluidos, en el instante $T_j$ ($1 \le j \le Q$).

Tarea

Dados la lentitud de cada participante y los datos de las $Q$ preguntas, escribe un programa que calcule el número de personas que cumplen la condición de cada pregunta.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene dos enteros separados por un espacio, $N$ y $Q$. Indican que hay $N$ participantes, sin incluir a IOI-chan, y $Q$ preguntas.
• La línea $i$ ($1 \le i \le N$) de las siguientes $N$ líneas contiene un entero $D_i$. Indica que el participante $i$, contando desde la cabeza de la fila, tiene lentitud $D_i$.
• La línea $j$ ($1 \le j \le Q$) de las siguientes $Q$ líneas contiene tres enteros separados por espacios, $T_j$, $L_j$ y $R_j$. Estos valores representan la pregunta $j$.

Salida

Escribe $Q$ líneas en la salida estándar. La línea $j$ ($1 \le j \le Q$) debe contener la respuesta a la pregunta $j$.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $1 \le N \le 500\,000$.
• $1 \le Q \le 500\,000$.
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $1 \le L_j \le R_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).

Subtareas

Hay 3 subtareas. La puntuación y las restricciones adicionales de cada una son las siguientes:

Subtarea 1 [7 puntos]

• $D_i=1$ ($1 \le i \le N$).

Subtarea 2 [12 puntos]

• $N \le 1\,000$.
• $Q \le 1\,000$.
• $T_j \le 1\,000$ ($1 \le j \le Q$).
• $1 \le L_j \le R_j \le 1\,000$ ($1 \le j \le Q$).

Subtarea 3 [81 puntos]

Sin restricciones adicionales.

Ejemplos

Entrada 1

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

Salida 1

0
1
1
2
1
2

Nota

En este ejemplo, los participantes e IOI-chan se mueven de la siguiente manera.

A continuación, el intervalo $[L,R]$ representa el conjunto de puntos de la recta cuyas coordenadas están entre $L$ y $R$, ambos incluidos.

• En el instante $0$, IOI-chan está en la coordenada $0$. Los participantes primero, segundo y tercero están en las coordenadas $-1$, $-2$ y $-3$, respectivamente.
• En el instante $1$, IOI-chan avanza hasta la coordenada $1$. Ningún participante se mueve; los participantes primero, segundo y tercero están en las coordenadas $-1$, $-2$ y $-3$, respectivamente. Como no hay ninguna persona en el intervalo $[2,4]$, se responde 0 a la primera pregunta.
• En el instante $2$, IOI-chan avanza hasta la coordenada $2$. Su distancia al primer participante pasa a ser $3$, por lo que este avanza hasta la coordenada $1$. Los participantes primero, segundo y tercero están en las coordenadas $1$, $-2$ y $-3$, respectivamente. Como solo IOI-chan está en el intervalo $[2,4]$, se responde 1 a la segunda pregunta.
• En el instante $3$, IOI-chan avanza hasta la coordenada $3$. Ningún participante se mueve; los participantes primero, segundo y tercero están en las coordenadas $1$, $-2$ y $-3$, respectivamente. Como solo IOI-chan está en el intervalo $[2,4]$, se responde 1 a la tercera pregunta.
• En el instante $4$, IOI-chan avanza hasta la coordenada $4$. Su distancia al primer participante pasa a ser $3$, por lo que este avanza hasta la coordenada $3$. Los participantes primero, segundo y tercero están en las coordenadas $3$, $-2$ y $-3$, respectivamente. Como IOI-chan y el primer participante están en el intervalo $[2,4]$, se responde 2 a la cuarta pregunta.
• En el instante $5$, IOI-chan avanza hasta la coordenada $5$. Ningún participante se mueve; los participantes primero, segundo y tercero están en las coordenadas $3$, $-2$ y $-3$, respectivamente. Como solo el primer participante está en el intervalo $[2,4]$, se responde 1 a la quinta pregunta.
• En el instante $6$, IOI-chan avanza hasta la coordenada $6$. Su distancia al primer participante pasa a ser $3$, por lo que este avanza hasta la coordenada $5$. Entonces la distancia entre los participantes primero y segundo pasa a ser $7$, por lo que el segundo avanza hasta la coordenada $4$. Además, la distancia entre los participantes segundo y tercero pasa a ser $7$, por lo que el tercero avanza hasta la coordenada $3$. Los participantes primero, segundo y tercero están en las coordenadas $5$, $4$ y $3$, respectivamente. Como los participantes segundo y tercero están en el intervalo $[2,4]$, se responde 2 a la sexta pregunta.

Entrada 2

4 2
1
1
1
1
2 1 4
1 3 6

Salida 2

2
0

Nota

Este ejemplo satisface las restricciones de la subtarea 1.

Entrada 3

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

Salida 3

1
6
0
5
2
7