Lors de la cérémonie d'ouverture de l'IOI 2018, $N$ concurrents défilent le long d'une file, représentée par une droite graduée. Tous les concurrents se dirigent dans le sens positif de la droite graduée. À l'instant $0$, le $i$-ème concurrent ($1 \le i \le N$, compté à partir de l'avant) se tient à la coordonnée $-i$. De plus, IOI-chan, la porte-drapeau, se tient à 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 se trouve à une distance supérieure ou égale à $D_i + 1$ de la personne (un concurrent ou IOI-chan) juste devant lui ou elle, le $i$-ème concurrent se déplace jusqu'à la position située à une distance $1$ de cette personne. Sinon, le $i$-ème concurrent ne se déplace pas.

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

Vous êtes un reporter 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. Il n'y avait rien d'autre à faire — vous avez décidé de tricher en prenant des photos de la salle, puis en dessinant les personnes dessus.

Afin de ne pas vous faire prendre en train de tricher, ou pour estimer le temps nécessaire pour dessiner les images, vous voulez connaître les $Q$ valeurs suivantes :

• le nombre de personnes se tenant à une coordonnée comprise entre $L_j$ et $R_j$ inclus à l'instant $T_j$ ($1 \le j \le Q$).

Tâche

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

Entrée

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

• La première ligne de l'entrée contient deux entiers séparés par un espace, $N$ et $Q$. 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 en partant de l'avant a une lenteur $D_i$.
• La $j$-ème ligne ($1 \le j \le Q$) des $Q$ lignes suivantes contient trois entiers séparés par des espaces, $T_j$, $L_j$ et $R_j$. 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$) de la sortie 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. Le score et les contraintes supplémentaires de chaque sous-tâche 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 pas de contraintes supplémentaires.

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 d'entrée, 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 la droite graduée dont la coordonnée est comprise entre $L$ et $R$ inclus.

• À l'instant $0$, IOI-chan se tient à la coordonnée $0$. Les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $-1$, $-2$ et $-3$.
• À l'instant $1$, IOI-chan se déplace à la coordonnée $1$. Aucun concurrent ne se déplace ; les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $-1$, $-2$ et $-3$. Comme il n'y a personne dans l'intervalle $[2, 4]$, affichez $0$ pour la 1re question.
• À l'instant $2$, IOI-chan se déplace à la coordonnée $2$. La distance entre IOI-chan et le 1er concurrent est maintenant de $3$, donc le 1er concurrent se déplace à la coordonnée $1$. Les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $1$, $-2$ et $-3$. Comme il n'y a qu'IOI-chan dans l'intervalle $[2, 4]$, affichez $1$ pour la 2e question.
• À l'instant $3$, IOI-chan se déplace à la coordonnée $3$. Aucun concurrent ne se déplace ; les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $1$, $-2$ et $-3$. Comme il n'y a qu'IOI-chan dans l'intervalle $[2, 4]$, affichez $1$ pour la 3e question.
• À l'instant $4$, IOI-chan se déplace à la coordonnée $4$. La distance entre IOI-chan et le 1er concurrent est maintenant de $3$, donc le 1er concurrent se déplace à la coordonnée $3$. Les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $3$, $-2$ et $-3$. Comme il y a IOI-chan et le 1er concurrent dans l'intervalle $[2, 4]$, affichez $2$ pour la 4e question.
• À l'instant $5$, IOI-chan se déplace à la coordonnée $5$. Aucun concurrent ne se déplace ; les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $3$, $-2$ et $-3$. Comme il n'y a que le 1er concurrent dans l'intervalle $[2, 4]$, affichez $1$ pour la 5e question.
• À l'instant $6$, IOI-chan se déplace à la coordonnée $6$. La distance entre IOI-chan et le 1er concurrent est maintenant de $3$, donc le 1er concurrent se déplace à la coordonnée $5$. Ensuite, la distance entre les 1er et 2e concurrents est maintenant de $7$, donc le 2e concurrent se déplace à la coordonnée $4$. De plus, la distance entre les 2e et 3e concurrents est maintenant de $7$, donc le 3e concurrent se déplace à la coordonnée $3$. Les 1er, 2e et 3e concurrents se tiennent respectivement aux coordonnées $5$, $4$ et $3$. Comme il y a les 2e et 3e concurrents dans l'intervalle $[2, 4]$, affichez $2$ pour la 6e question.

Entrée 2

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

Sortie 2

2
0

Remarque

Cet exemple d'entrée 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