Við opnunarhátíð IOI 2018 ganga $N$ keppendur eftir línu sem táknuð er með talnalínu. Allir keppendur stefna í jákvæða átt talnalínunnar. Á tíma $0$ stendur $i$-ti keppandinn ($1 \le i \le N$, talið fremst frá) í hniti $-i$. Að auki stendur IOI-chan, fánaberinn, í hniti $0$.

Hver keppandi hefur gildi sem kallast seingangur. $i$-ti keppandinn hefur seingang $D_i$. Keppendurnir fylgja eftirfarandi reglu:

• Ef $i$-ti keppandinn er í fjarlægð sem er stærri en eða jöfn $D_i+1$ frá manneskjunni (keppanda eða IOI-chan) sem er beint fyrir framan hann eða hana, færir $i$-ti keppandinn sig á staðinn sem er í fjarlægð $1$ frá þeirri manneskju. Annars hreyfir $i$-ti keppandinn sig ekki.

IOI-chan færist um vegalengdina $1$ í jákvæða átt á línunni á hverri tímaeiningu. Keppandi færist samstundis í hvert sinn sem skilyrðið hér að ofan er uppfyllt.

Þú ert blaðamaður sem á að fjalla um opnunarhátíðina. Þú áttir að taka myndir, en þú svafst fast alla hátíðina. Það var ekkert hægt að gera við því — þú ákvaðst að svindla með því að taka myndir af salnum og teikna svo myndir af fólkinu inn á þær.

Til þess að upp um svindlið komist ekki, eða til að áætla tímann sem tekur að teikna myndirnar, viltu vita eftirfarandi $Q$ gildi:

• fjölda fólks sem stendur í hniti á milli $L_j$ og $R_j$, báðir endar meðtaldir, á tíma $T_j$ ($1 \le j \le Q$).

Verkefni

Gefinn er seingangur hvers keppanda og gögnin fyrir $Q$ spurningarnar. Skrifið forrit sem reiknar út fjölda fólks sem uppfyllir skilyrðið fyrir hverja spurningu.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

• Fyrsta línan í inntakinu inniheldur tvær heiltölur $N$ og $Q$ aðskildar með bili. Þetta þýðir að það eru $N$ keppendur (IOI-chan ekki meðtalin) og $Q$ spurningar.
• $i$-ta línan ($1 \le i \le N$) af næstu $N$ línum inniheldur heiltölu $D_i$. Þetta þýðir að $i$-ti keppandinn fremst frá hefur seingang $D_i$.
• $j$-ta línan ($1 \le j \le Q$) af næstu $Q$ línum inniheldur þrjár heiltölur $T_j$, $L_j$ og $R_j$ aðskildar með bilum. Þessi gildi tákna $j$-tu spurninguna.

Úttak

Skrifið $Q$ línur í staðalúttak. $j$-ta línan ($1 \le j \le Q$) í úttakinu á að innihalda svarið við $j$-tu spurningunni.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

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

Undirverkefni

Það eru 3 undirverkefni. Stigagjöf og viðbótarskorður hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [7 stig]

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

Undirverkefni 2 [12 stig]

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

Undirverkefni 3 [81 stig]

Það eru engar viðbótarskorður.

Dæmi

Inntak 1

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

Úttak 1

0
1
1
2
1
2

Athugasemd

Í þessu sýnidæmi hreyfast keppendurnir og IOI-chan sem hér segir.

Í framhaldinu táknar bilið $[L,R]$ mengi punkta með hnit á milli $L$ og $R$, báðir endar meðtaldir, á talnalínunni.

• Á tíma $0$ stendur IOI-chan í hniti $0$. 1., 2. og 3. keppandinn standa í hnitum $-1$, $-2$ og $-3$, í sömu röð.
• Á tíma $1$ færir IOI-chan sig í hnit $1$. Engir keppendur hreyfa sig; 1., 2. og 3. keppandinn standa í hnitum $-1$, $-2$ og $-3$, í sömu röð. Þar sem enginn er á bilinu $[2,4]$ skal prenta 0 fyrir 1. spurninguna.
• Á tíma $2$ færir IOI-chan sig í hnit $2$. Fjarlægðin milli IOI-chan og 1. keppandans er nú $3$, svo 1. keppandinn færir sig í hnit $1$. 1., 2. og 3. keppandinn standa í hnitum $1$, $-2$ og $-3$, í sömu röð. Þar sem aðeins IOI-chan er á bilinu $[2,4]$ skal prenta 1 fyrir 2. spurninguna.
• Á tíma $3$ færir IOI-chan sig í hnit $3$. Engir keppendur hreyfa sig; 1., 2. og 3. keppandinn standa í hnitum $1$, $-2$ og $-3$, í sömu röð. Þar sem aðeins IOI-chan er á bilinu $[2,4]$ skal prenta 1 fyrir 3. spurninguna.
• Á tíma $4$ færir IOI-chan sig í hnit $4$. Fjarlægðin milli IOI-chan og 1. keppandans er nú $3$, svo 1. keppandinn færir sig í hnit $3$. 1., 2. og 3. keppandinn standa í hnitum $3$, $-2$ og $-3$, í sömu röð. Þar sem IOI-chan og 1. keppandinn eru á bilinu $[2,4]$ skal prenta 2 fyrir 4. spurninguna.
• Á tíma $5$ færir IOI-chan sig í hnit $5$. Engir keppendur hreyfa sig; 1., 2. og 3. keppandinn standa í hnitum $3$, $-2$ og $-3$, í sömu röð. Þar sem aðeins 1. keppandinn er á bilinu $[2,4]$ skal prenta 1 fyrir 5. spurninguna.
• Á tíma $6$ færir IOI-chan sig í hnit $6$. Fjarlægðin milli IOI-chan og 1. keppandans er nú $3$, svo 1. keppandinn færir sig í hnit $5$. Þá er fjarlægðin milli 1. og 2. keppandans orðin $7$, svo 2. keppandinn færir sig í hnit $4$. Ennfremur er fjarlægðin milli 2. og 3. keppandans nú $7$, svo 3. keppandinn færir sig í hnit $3$. 1., 2. og 3. keppandinn standa í hnitum $5$, $4$ og $3$, í sömu röð. Þar sem 2. og 3. keppandinn eru á bilinu $[2,4]$ skal prenta 2 fyrir 6. spurninguna.

Inntak 2

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

Úttak 2

2
0

Athugasemd

Þetta sýnidæmi uppfyllir skorður fyrir undirverkefni 1.

Inntak 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

Úttak 3

1
6
0
5
2
7