Under öppningsceremonin för IOI 2018 marscherar $N$ tävlande längs en linje som representeras av en tallinje. Alla tävlande rör sig i tallinjens positiva riktning. Vid tidpunkten $0$ står den $i$-te tävlande ($1 \le i \le N$, räknat framifrån) på koordinaten $-i$. Dessutom står IOI-chan, fanbäraren, på koordinaten $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 som är 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 den $i$-te tävlande inte.

IOI-chan förflyttar sig sträckan $1$ i positiv riktning längs linjen per tidsenhet. En tävlande förflyttar sig omedelbart så snart villkoret ovan är uppfyllt.

Du är en reporter som ska bevaka öppningsceremonin. Du skulle ta foton, men du sov djupt under hela ceremonin. Det var inget att göra åt saken — du bestämde dig för att fuska genom att ta foton av salen och sedan rita dit bilder av personerna 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 samt data för de $Q$ frågorna, skriv ett program som för varje fråga beräknar antalet personer som uppfyller villkoret.

Indata

Läs in 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 ut $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

All 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 följande:

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

Förklaring

I detta exempel på indata rör sig de tävlande och IOI-chan på följande sätt.

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

• Vid tidpunkten $0$ står IOI-chan på koordinaten $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 koordinaten $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 koordinaten $2$. Avståndet mellan IOI-chan och den 1:a tävlande är nu $3$, så den 1:a tävlande flyttar sig till koordinaten $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 koordinaten $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 koordinaten $4$. Avståndet mellan IOI-chan och den 1:a tävlande är nu $3$, så den 1:a tävlande flyttar sig till koordinaten $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 koordinaten $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 koordinaten $6$. Avståndet mellan IOI-chan och den 1:a tävlande är nu $3$, så den 1:a tävlande flyttar sig till koordinaten $5$. Då är avståndet mellan den 1:a och den 2:a tävlande $7$, så den 2:a tävlande flyttar sig till koordinaten $4$. Dessutom är avståndet mellan den 2:a och den 3:e tävlande nu $7$, så den 3:e tävlande flyttar sig till koordinaten $3$. Den 1:a, 2:a och 3:e tävlande står på koordinaterna $5$, $4$ respektive $3$. Eftersom den 2:a och den 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

Förklaring

Detta exempel på indata 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