Vid öppningsceremonin för IOI 2018 marscherar $N$ tävlande längs en linje, som representeras av en tallinje. Alla tävlande går i tallinjens positiva riktning. Vid tidpunkten $0$ står den $i$-te tävlande ($1 \le i \le N$, räknat framifrån) på koordinat $-i$. Dessutom står IOI-chan, fanbäraren, på koordinat $0$.

Varje tävlande har ett värde som kallas långsamhet. Den $i$-te tävlande har långsamheten $D_i$. De tävlande följer följande regel:

• Om den $i$-te tävlande befinner sig på ett avstånd större än eller lika med $D_i+1$ från personen (en tävlande eller IOI-chan) precis framför honom eller henne, flyttar sig den $i$-te tävlande till positionen på avståndet $1$ från den personen. Annars flyttar sig inte den $i$-te tävlande.

IOI-chan flyttar sig sträckan $1$ i positiv riktning på linjen per tidsenhet. En tävlande flyttar sig omedelbart så fort villkoret som beskrivs ovan är uppfyllt.

Du är en reporter som ska bevaka öppningsceremonin. Du skulle ta foton, men du sov djupt under hela ceremonin. Det kunde inte hjälpas — du bestämde dig för att fuska genom att ta foton av hallen och sedan rita dit bilder av människorna på dem.

För att inte bli påkommen med att fuska, eller för att uppskatta tiden det tar att rita bilderna, vill du veta följande $Q$ värden:

• antalet personer som står på en koordinat mellan $L_j$ och $R_j$, inklusive gränserna, vid tidpunkten $T_j$ ($1 \le j \le Q$).

Uppgift

Givet långsamheten för varje tävlande och data för de $Q$ frågorna, skriv ett program som beräknar antalet personer som uppfyller villkoret för varje fråga.

Indata

Läs följande data från standard inmatning.

• Den första raden i indata innehåller två blankstegsseparerade heltal $N$ och $Q$. Detta betyder att det finns $N$ tävlande (exklusive IOI-chan) och att det finns $Q$ frågor.
• Den $i$-te raden ($1 \le i \le N$) av de följande $N$ raderna innehåller ett heltal $D_i$. Detta betyder att den $i$-te tävlande framifrån har långsamheten $D_i$.
• Den $j$-te raden ($1 \le j \le Q$) av de följande $Q$ raderna innehåller tre blankstegsseparerade heltal $T_j$, $L_j$ och $R_j$. Dessa värden representerar den $j$-te frågan.

Utdata

Skriv $Q$ rader till standard utmatning. Den $j$-te raden ($1 \le j \le Q$) i utdata ska innehålla svaret på den $j$-te frågan.

Begränsningar

Alla indata uppfyller följande villkor.

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

Deluppgifter

Det finns 3 deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är som följer:

Deluppgift 1 [7 poäng]

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

Deluppgift 2 [12 poäng]

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

Deluppgift 3 [81 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

0
1
1
2
1
2

Anmärkning

I detta exempel flyttar sig de tävlande och IOI-chan enligt följande.

I det följande betecknar intervallet $[L,R]$ mängden av punkter med koordinat mellan $L$ och $R$, inklusive gränserna, på tallinjen.

• Vid tidpunkten $0$ står IOI-chan på koordinat $0$. Den 1:a, 2:a och 3:e tävlande står på koordinaterna $-1$, $-2$ respektive $-3$.
• Vid tidpunkten $1$ flyttar sig IOI-chan till koordinat $1$. Inga tävlande flyttar sig; den 1:a, 2:a och 3:e tävlande står på koordinaterna $-1$, $-2$ respektive $-3$. Eftersom det inte finns några personer i intervallet $[2,4]$, skriv ut 0 för den 1:a frågan.
• Vid tidpunkten $2$ flyttar sig IOI-chan till koordinat $2$. Avståndet mellan IOI-chan och den 1:a tävlande är nu $3$, så den 1:a tävlande flyttar sig till koordinat $1$. Den 1:a, 2:a och 3:e tävlande står på koordinaterna $1$, $-2$ respektive $-3$. Eftersom endast IOI-chan befinner sig i intervallet $[2,4]$, skriv ut 1 för den 2:a frågan.
• Vid tidpunkten $3$ flyttar sig IOI-chan till koordinat $3$. Inga tävlande flyttar sig; den 1:a, 2:a och 3:e tävlande står på koordinaterna $1$, $-2$ respektive $-3$. Eftersom endast IOI-chan befinner sig i intervallet $[2,4]$, skriv ut 1 för den 3:e frågan.
• Vid tidpunkten $4$ flyttar sig IOI-chan till koordinat $4$. Avståndet mellan IOI-chan och den 1:a tävlande är nu $3$, så den 1:a tävlande flyttar sig till koordinat $3$. Den 1:a, 2:a och 3:e tävlande står på koordinaterna $3$, $-2$ respektive $-3$. Eftersom IOI-chan och den 1:a tävlande befinner sig i intervallet $[2,4]$, skriv ut 2 för den 4:e frågan.
• Vid tidpunkten $5$ flyttar sig IOI-chan till koordinat $5$. Inga tävlande flyttar sig; den 1:a, 2:a och 3:e tävlande står på koordinaterna $3$, $-2$ respektive $-3$. Eftersom endast den 1:a tävlande befinner sig i intervallet $[2,4]$, skriv ut 1 för den 5:e frågan.
• Vid tidpunkten $6$ flyttar sig IOI-chan till koordinat $6$. Avståndet mellan IOI-chan och den 1:a tävlande är nu $3$, så den 1:a tävlande flyttar sig till koordinat $5$. Då är avståndet mellan den 1:a och 2:a tävlande nu $7$, så den 2:a tävlande flyttar sig till koordinat $4$. Vidare är avståndet mellan den 2:a och 3:e tävlande nu $7$, så den 3:e tävlande flyttar sig till koordinat $3$. Den 1:a, 2:a och 3:e tävlande står på koordinaterna $5$, $4$ respektive $3$. Eftersom den 2:a och 3:e tävlande befinner sig i intervallet $[2,4]$, skriv ut 2 för den 6:e frågan.

Indata 2

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

Utdata 2

2
0

Anmärkning

Detta exempel uppfyller begränsningarna för deluppgift 1.

Indata 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

Utdata 3

1
6
0
5
2
7