Under åpningsseremonien til IOI 2018 marsjerer $N$ deltakere langs en linje, som er representert ved en tallinje. Alle deltakerne går i den positive retningen på tallinjen. Ved tidspunkt $0$ står den $i$-te deltakeren ($1 \le i \le N$, telt forfra) på koordinat $-i$. I tillegg står IOI-chan, flaggbæreren, på koordinat $0$.

Hver deltaker har en verdi som kalles treghet. Den $i$-te deltakeren har treghet $D_i$. Deltakerne følger følgende regel:

• Hvis den $i$-te deltakeren er i en avstand større enn eller lik $D_i+1$ fra personen (en deltaker eller IOI-chan) rett foran ham eller henne, flytter den $i$-te deltakeren seg til posisjonen med avstand $1$ fra denne personen. Ellers flytter ikke den $i$-te deltakeren seg.

IOI-chan flytter seg en avstand $1$ i positiv retning på linjen per tidsenhet. En deltaker flytter seg umiddelbart hver gang betingelsen beskrevet ovenfor er oppfylt.

Du er en reporter som skal dekke åpningsseremonien. Du måtte ta bilder, men du sov tungt gjennom hele seremonien. Det var ikke noe å gjøre med det — du bestemte deg for å jukse ved å ta bilder av salen og deretter tegne inn bilder av menneskene på dem.

For ikke å bli tatt i juks, eller for å beregne tiden det tar å tegne bildene, vil du vite følgende $Q$ verdier:

• antallet personer som står på en koordinat mellom $L_j$ og $R_j$, inkludert ytterpunktene, ved tidspunkt $T_j$ ($1 \le j \le Q$).

Oppgave

Gitt tregheten til hver deltaker og dataene for de $Q$ spørsmålene, skriv et program som beregner antallet personer som oppfyller betingelsen for hvert spørsmål.

Inndata

Les følgende data fra standard inndata.

• Den første linjen i inndata inneholder to mellomromseparerte heltall $N$ og $Q$. Dette betyr at det er $N$ deltakere (ikke inkludert IOI-chan) og at det er $Q$ spørsmål.
• Den $i$-te linjen ($1 \le i \le N$) av de neste $N$ linjene inneholder et heltall $D_i$. Dette betyr at den $i$-te deltakeren forfra har treghet $D_i$.
• Den $j$-te linjen ($1 \le j \le Q$) av de neste $Q$ linjene inneholder tre mellomromseparerte heltall $T_j$, $L_j$ og $R_j$. Disse verdiene representerer det $j$-te spørsmålet.

Utdata

Skriv $Q$ linjer til standard utdata. Den $j$-te linjen ($1 \le j \le Q$) i utdata skal inneholde svaret på det $j$-te spørsmålet.

Begrensninger

Alle inndata oppfyller følgende betingelser.

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

Deloppgaver

Det er 3 deloppgaver. Poengsummen og tilleggsbegrensningene for hver deloppgave er som følger:

Deloppgave 1 [7 poeng]

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

Deloppgave 2 [12 poeng]

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

Deloppgave 3 [81 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 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

Merk

I dette eksempelet flytter deltakerne og IOI-chan seg som følger.

I det følgende betegner intervallet $[L,R]$ mengden av punkter med koordinat mellom $L$ og $R$, inkludert ytterpunktene, på tallinjen.

• Ved tidspunkt $0$ står IOI-chan på koordinat $0$. Den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $-1$, $-2$ og $-3$.
• Ved tidspunkt $1$ flytter IOI-chan seg til koordinat $1$. Ingen deltakere flytter seg; den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $-1$, $-2$ og $-3$. Siden det ikke er noen personer i intervallet $[2,4]$, skriv ut 0 for det 1. spørsmålet.
• Ved tidspunkt $2$ flytter IOI-chan seg til koordinat $2$. Avstanden mellom IOI-chan og den 1. deltakeren er nå $3$, så den 1. deltakeren flytter seg til koordinat $1$. Den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $1$, $-2$ og $-3$. Siden det bare er IOI-chan i intervallet $[2,4]$, skriv ut 1 for det 2. spørsmålet.
• Ved tidspunkt $3$ flytter IOI-chan seg til koordinat $3$. Ingen deltakere flytter seg; den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $1$, $-2$ og $-3$. Siden det bare er IOI-chan i intervallet $[2,4]$, skriv ut 1 for det 3. spørsmålet.
• Ved tidspunkt $4$ flytter IOI-chan seg til koordinat $4$. Avstanden mellom IOI-chan og den 1. deltakeren er nå $3$, så den 1. deltakeren flytter seg til koordinat $3$. Den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $3$, $-2$ og $-3$. Siden både IOI-chan og den 1. deltakeren er i intervallet $[2,4]$, skriv ut 2 for det 4. spørsmålet.
• Ved tidspunkt $5$ flytter IOI-chan seg til koordinat $5$. Ingen deltakere flytter seg; den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $3$, $-2$ og $-3$. Siden det bare er den 1. deltakeren i intervallet $[2,4]$, skriv ut 1 for det 5. spørsmålet.
• Ved tidspunkt $6$ flytter IOI-chan seg til koordinat $6$. Avstanden mellom IOI-chan og den 1. deltakeren er nå $3$, så den 1. deltakeren flytter seg til koordinat $5$. Deretter er avstanden mellom den 1. og 2. deltakeren nå $7$, så den 2. deltakeren flytter seg til koordinat $4$. Videre er avstanden mellom den 2. og 3. deltakeren nå $7$, så den 3. deltakeren flytter seg til koordinat $3$. Den 1., 2. og 3. deltakeren står på henholdsvis koordinatene $5$, $4$ og $3$. Siden den 2. og 3. deltakeren er i intervallet $[2,4]$, skriv ut 2 for det 6. spørsmålet.

Inndata 2

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

Utdata 2

2
0

Merk

Dette inndataeksempelet oppfyller betingelsene for deloppgave 1.

Inndata 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