Lors de la cérémonie d'ouverture des IOI 2018, $N$ concurrents défilent en file sur une ligne, représentée par un axe numérique. Tous avancent dans le sens positif de cet axe. À l'instant $0$, le $i$-ème concurrent ($1 \le i \le N$, en comptant depuis la tête de la file) se trouve à la coordonnée $-i$. De plus, IOI-chan, qui porte le drapeau, se trouve à la coordonnée $0$.

Chaque concurrent possède une valeur appelée lenteur. Le $i$-ème concurrent a une lenteur $D_i$. Les concurrents respectent la règle suivante :

• Si le $i$-ème concurrent est à une distance supérieure ou égale à $D_i+1$ de la personne (un concurrent ou IOI-chan) immédiatement devant lui, il se déplace jusqu'à la position située à une distance de $1$ de cette personne. Sinon, il ne bouge pas.

IOI-chan parcourt une distance de $1$ dans le sens positif de l'axe par unité de temps. Un concurrent se déplace instantanément dès que la condition ci-dessus est satisfaite.

Vous êtes un journaliste chargé de couvrir la cérémonie d'ouverture. Vous deviez prendre des photos, mais vous avez dormi profondément pendant toute la cérémonie. Ne pouvant rien y faire, vous décidez de tricher en photographiant la salle, puis en dessinant les personnes sur les photos.

Pour éviter que votre supercherie soit découverte, ou pour estimer le temps nécessaire aux dessins, vous souhaitez connaître les $Q$ valeurs suivantes :

• Le nombre de personnes dont la coordonnée est comprise entre $L_j$ et $R_j$, bornes incluses, à l'instant $T_j$ ($1 \le j \le Q$).

Tâche

Étant données la lenteur de chaque concurrent et les données des $Q$ questions, écrivez un programme qui calcule, pour chaque question, le nombre de personnes satisfaisant la condition.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient deux entiers $N$ et $Q$ séparés par un espace. Cela signifie qu'il y a $N$ concurrents, sans compter IOI-chan, et $Q$ questions.
• La $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes contient un entier $D_i$. Cela signifie que le $i$-ème concurrent depuis la tête de la file a une lenteur $D_i$.
• La $j$-ème ligne ($1 \le j \le Q$) des $Q$ lignes suivantes contient trois entiers $T_j$, $L_j$ et $R_j$ séparés par des espaces. Ces valeurs représentent la $j$-ème question.

Sortie

Écrivez $Q$ lignes sur la sortie standard. La $j$-ème ligne ($1 \le j \le Q$) doit contenir la réponse à la $j$-ème question.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $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$).

Sous-tâches

Il y a 3 sous-tâches. Leurs scores et contraintes supplémentaires sont les suivants :

Sous-tâche 1 [7 points]

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

Sous-tâche 2 [12 points]

• $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$).

Sous-tâche 3 [81 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

0
1
1
2
1
2

Remarque

Dans cet exemple, les concurrents et IOI-chan se déplacent comme suit.

Dans ce qui suit, l'intervalle $[L,R]$ désigne l'ensemble des points de l'axe numérique dont les coordonnées sont comprises entre $L$ et $R$, bornes incluses.

• À l'instant $0$, IOI-chan se trouve à la coordonnée $0$. Les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $-1$, $-2$ et $-3$.
• À l'instant $1$, IOI-chan se déplace à la coordonnée $1$. Aucun concurrent ne bouge ; les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $-1$, $-2$ et $-3$. Comme personne ne se trouve dans l'intervalle $[2,4]$, il faut afficher $0$ pour la première question.
• À l'instant $2$, IOI-chan se déplace à la coordonnée $2$. La distance entre IOI-chan et le premier concurrent vaut alors $3$, donc celui-ci se déplace à la coordonnée $1$. Les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $1$, $-2$ et $-3$. Comme seule IOI-chan se trouve dans l'intervalle $[2,4]$, il faut afficher $1$ pour la deuxième question.
• À l'instant $3$, IOI-chan se déplace à la coordonnée $3$. Aucun concurrent ne bouge ; les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $1$, $-2$ et $-3$. Comme seule IOI-chan se trouve dans l'intervalle $[2,4]$, il faut afficher $1$ pour la troisième question.
• À l'instant $4$, IOI-chan se déplace à la coordonnée $4$. La distance entre IOI-chan et le premier concurrent vaut alors $3$, donc celui-ci se déplace à la coordonnée $3$. Les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $3$, $-2$ et $-3$. Comme IOI-chan et le premier concurrent se trouvent dans l'intervalle $[2,4]$, il faut afficher $2$ pour la quatrième question.
• À l'instant $5$, IOI-chan se déplace à la coordonnée $5$. Aucun concurrent ne bouge ; les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $3$, $-2$ et $-3$. Comme seul le premier concurrent se trouve dans l'intervalle $[2,4]$, il faut afficher $1$ pour la cinquième question.
• À l'instant $6$, IOI-chan se déplace à la coordonnée $6$. La distance entre IOI-chan et le premier concurrent vaut alors $3$, donc celui-ci se déplace à la coordonnée $5$. La distance entre les premier et deuxième concurrents vaut alors $7$, donc le deuxième concurrent se déplace à la coordonnée $4$. De plus, la distance entre les deuxième et troisième concurrents vaut alors $7$, donc le troisième concurrent se déplace à la coordonnée $3$. Les premier, deuxième et troisième concurrents se trouvent respectivement aux coordonnées $5$, $4$ et $3$. Comme les deuxième et troisième concurrents se trouvent dans l'intervalle $[2,4]$, il faut afficher $2$ pour la sixième question.

Entrée 2

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

Sortie 2

2
0

Remarque

Cet exemple satisfait les contraintes de la sous-tâche $1$.

Entrée 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

Sortie 3

1
6
0
5
2
7