Bei der Eröffnungsfeier der IOI 2018 marschieren $N$ Teilnehmer entlang einer Geraden, die durch einen Zahlenstrahl dargestellt wird. Alle Teilnehmer bewegen sich in dessen positive Richtung. Zum Zeitpunkt $0$ steht der $i$-te Teilnehmer ($1 \le i \le N$, von vorne gezählt) an der Koordinate $-i$. Außerdem steht die Fahnenträgerin IOI-chan an der Koordinate $0$.

Jeder Teilnehmer hat einen Wert namens Trägheit. Der $i$-te Teilnehmer hat die Trägheit $D_i$. Die Teilnehmer halten sich an folgende Regel:

• Wenn der Abstand des $i$-ten Teilnehmers zur unmittelbar vor ihm stehenden Person (einem Teilnehmer oder IOI-chan) mindestens $D_i+1$ beträgt, bewegt er sich an die Position im Abstand $1$ hinter dieser Person. Andernfalls bewegt er sich nicht.

IOI-chan bewegt sich pro Zeiteinheit um die Strecke $1$ in positive Richtung. Ein Teilnehmer bewegt sich augenblicklich, sobald die oben beschriebene Bedingung erfüllt ist.

Du bist ein Reporter, der über die Eröffnungsfeier berichten soll. Du solltest Fotos machen, hast aber während der gesamten Feier fest geschlafen. Es hilft nichts: Du beschließt zu schummeln, indem du die Halle fotografierst und anschließend die Personen in die Fotos zeichnest.

Um beim Schummeln nicht erwischt zu werden oder die zum Zeichnen benötigte Zeit abzuschätzen, möchtest du die folgenden $Q$ Werte wissen:

• die Anzahl der Personen, die zum Zeitpunkt $T_j$ ($1 \le j \le Q$) an einer Koordinate zwischen $L_j$ und $R_j$ einschließlich beider Grenzen stehen.

Aufgabe

Schreibe ein Programm, das aus der Trägheit jedes Teilnehmers und den Angaben der $Q$ Fragen für jede Frage die Anzahl der Personen berechnet, die die Bedingung erfüllen.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $N$ und $Q$. Dies bedeutet, dass es $N$ Teilnehmer (ohne IOI-chan) und $Q$ Fragen gibt.
• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält eine ganze Zahl $D_i$. Der $i$-te Teilnehmer von vorne hat die Trägheit $D_i$.
• Die $j$-te Zeile ($1 \le j \le Q$) der folgenden $Q$ Zeilen enthält drei durch Leerzeichen getrennte ganze Zahlen $T_j$, $L_j$ und $R_j$. Diese Werte beschreiben die $j$-te Frage.

Ausgabe

Schreibe $Q$ Zeilen auf die Standardausgabe. Die $j$-te Ausgabezeile ($1 \le j \le Q$) soll die Antwort auf die $j$-te Frage enthalten.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Es gibt 3 Teilaufgaben. Ihre Punktzahlen und zusätzlichen Beschränkungen sind wie folgt:

Teilaufgabe 1 [7 Punkte]

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

Teilaufgabe 2 [12 Punkte]

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

Teilaufgabe 3 [81 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

0
1
1
2
1
2

Hinweis

In diesem Beispiel bewegen sich die Teilnehmer und IOI-chan wie folgt.

Im Folgenden bezeichnet das Intervall $[L,R]$ die Menge der Punkte auf dem Zahlenstrahl, deren Koordinaten zwischen $L$ und $R$ einschließlich beider Grenzen liegen.

• Zum Zeitpunkt $0$ steht IOI-chan an der Koordinate $0$. Der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $-1$, $-2$ beziehungsweise $-3$.
• Zum Zeitpunkt $1$ bewegt sich IOI-chan zur Koordinate $1$. Kein Teilnehmer bewegt sich; der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $-1$, $-2$ beziehungsweise $-3$. Da sich keine Person im Intervall $[2,4]$ befindet, gib für die 1. Frage 0 aus.
• Zum Zeitpunkt $2$ bewegt sich IOI-chan zur Koordinate $2$. Der Abstand zwischen IOI-chan und dem 1. Teilnehmer beträgt nun $3$, also bewegt sich der 1. Teilnehmer zur Koordinate $1$. Der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $1$, $-2$ beziehungsweise $-3$. Da sich nur IOI-chan im Intervall $[2,4]$ befindet, gib für die 2. Frage 1 aus.
• Zum Zeitpunkt $3$ bewegt sich IOI-chan zur Koordinate $3$. Kein Teilnehmer bewegt sich; der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $1$, $-2$ beziehungsweise $-3$. Da sich nur IOI-chan im Intervall $[2,4]$ befindet, gib für die 3. Frage 1 aus.
• Zum Zeitpunkt $4$ bewegt sich IOI-chan zur Koordinate $4$. Der Abstand zwischen IOI-chan und dem 1. Teilnehmer beträgt nun $3$, also bewegt sich der 1. Teilnehmer zur Koordinate $3$. Der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $3$, $-2$ beziehungsweise $-3$. Da sich IOI-chan und der 1. Teilnehmer im Intervall $[2,4]$ befinden, gib für die 4. Frage 2 aus.
• Zum Zeitpunkt $5$ bewegt sich IOI-chan zur Koordinate $5$. Kein Teilnehmer bewegt sich; der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $3$, $-2$ beziehungsweise $-3$. Da sich nur der 1. Teilnehmer im Intervall $[2,4]$ befindet, gib für die 5. Frage 1 aus.
• Zum Zeitpunkt $6$ bewegt sich IOI-chan zur Koordinate $6$. Der Abstand zwischen IOI-chan und dem 1. Teilnehmer beträgt nun $3$, also bewegt sich der 1. Teilnehmer zur Koordinate $5$. Dann beträgt der Abstand zwischen dem 1. und dem 2. Teilnehmer $7$, also bewegt sich der 2. Teilnehmer zur Koordinate $4$. Außerdem beträgt der Abstand zwischen dem 2. und dem 3. Teilnehmer nun $7$, also bewegt sich der 3. Teilnehmer zur Koordinate $3$. Der 1., 2. und 3. Teilnehmer stehen an den Koordinaten $5$, $4$ beziehungsweise $3$. Da sich der 2. und der 3. Teilnehmer im Intervall $[2,4]$ befinden, gib für die 6. Frage 2 aus.

Eingabe 2

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

Ausgabe 2

2
0

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen von Teilaufgabe 1.

Eingabe 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

Ausgabe 3

1
6
0
5
2
7