IOI 2018 -kilpailun avajaisissa $N$ kilpailijaa marssii suoraa pitkin, jota kuvataan lukusuoralla. Kaikki kilpailijat kulkevat lukusuoran positiiviseen suuntaan. Ajanhetkellä $0$ $i$. kilpailija ($1 \le i \le N$, edestä laskettuna) seisoo koordinaatissa $-i$. Lisäksi lipunkantaja IOI-chan seisoo koordinaatissa $0$.

Jokaisella kilpailijalla on arvo, jota kutsutaan hitaudeksi. $i$. kilpailijan hitaus on $D_i$. Kilpailijat noudattavat seuraavaa sääntöä:

• Jos $i$. kilpailija on vähintään etäisyydellä $D_i+1$ suoraan hänen edessään olevasta henkilöstä (kilpailijasta tai IOI-chanista), $i$. kilpailija siirtyy kohtaan, joka on etäisyydellä $1$ kyseisestä henkilöstä. Muussa tapauksessa $i$. kilpailija ei liiku.

IOI-chan liikkuu lukusuoralla positiiviseen suuntaan matkan $1$ aikayksikköä kohti. Kilpailija siirtyy välittömästi aina, kun yllä kuvattu ehto täyttyy.

Olet toimittaja, jonka tehtävänä on raportoida avajaisista. Sinun piti ottaa valokuvia, mutta nukuit sikeästi koko avajaisten ajan. Sille ei voinut mitään — päätit huijata ottamalla valokuvia salista ja piirtämällä niihin ihmisten kuvat jälkikäteen.

Jotta et jäisi kiinni huijaamisesta, tai arvioidaksesi kuvien piirtämiseen kuluvaa aikaa, haluat tietää seuraavat $Q$ arvoa:

• niiden henkilöiden lukumäärä, jotka seisovat koordinaattien $L_j$ ja $R_j$ välissä (päätepisteet mukaan lukien) ajanhetkellä $T_j$ ($1 \le j \le Q$).

Tehtävä

Kun annetaan kunkin kilpailijan hitaus ja $Q$ kysymyksen tiedot, kirjoita ohjelma, joka laskee ehdon täyttävien henkilöiden lukumäärän kullekin kysymykselle.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Syötteen ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $Q$. Tämä tarkoittaa, että kilpailijoita on $N$ (ilman IOI-chania) ja kysymyksiä on $Q$.
• Seuraavien $N$ rivin $i$. rivi ($1 \le i \le N$) sisältää kokonaisluvun $D_i$. Tämä tarkoittaa, että edestä lukien $i$. kilpailijan hitaus on $D_i$.
• Seuraavien $Q$ rivin $j$. rivi ($1 \le j \le Q$) sisältää kolme välilyönnillä erotettua kokonaislukua $T_j$, $L_j$ ja $R_j$. Nämä arvot kuvaavat $j$. kysymystä.

Tuloste

Kirjoita vakiontulosteeseen $Q$ riviä. Tulosteen $j$. rivin ($1 \le j \le Q$) tulee sisältää vastaus $j$. kysymykseen.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

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

Osatehtävät

Tehtävässä on 3 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [7 pistettä]

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

Osatehtävä 2 [12 pistettä]

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

Osatehtävä 3 [81 pistettä]

Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

0
1
1
2
1
2

Huomautus

Tässä esimerkkisyötteessä kilpailijat ja IOI-chan liikkuvat seuraavasti.

Seuraavassa väli $[L,R]$ tarkoittaa lukusuoran niiden pisteiden joukkoa, joiden koordinaatti on välillä $L$ ja $R$, päätepisteet mukaan lukien.

• Ajanhetkellä $0$ IOI-chan seisoo koordinaatissa $0$. 1., 2. ja 3. kilpailija seisovat koordinaateissa $-1$, $-2$ ja $-3$, vastaavasti.
• Ajanhetkellä $1$ IOI-chan siirtyy koordinaattiin $1$. Kukaan kilpailijoista ei liiku; 1., 2. ja 3. kilpailija seisovat koordinaateissa $-1$, $-2$ ja $-3$. Koska välillä $[2,4]$ ei ole ketään, tulosta 0 1. kysymykseen.
• Ajanhetkellä $2$ IOI-chan siirtyy koordinaattiin $2$. IOI-chanin ja 1. kilpailijan välinen etäisyys on nyt $3$, joten 1. kilpailija siirtyy koordinaattiin $1$. 1., 2. ja 3. kilpailija seisovat koordinaateissa $1$, $-2$ ja $-3$. Koska välillä $[2,4]$ on vain IOI-chan, tulosta 1 2. kysymykseen.
• Ajanhetkellä $3$ IOI-chan siirtyy koordinaattiin $3$. Kukaan kilpailijoista ei liiku; 1., 2. ja 3. kilpailija seisovat koordinaateissa $1$, $-2$ ja $-3$. Koska välillä $[2,4]$ on vain IOI-chan, tulosta 1 3. kysymykseen.
• Ajanhetkellä $4$ IOI-chan siirtyy koordinaattiin $4$. IOI-chanin ja 1. kilpailijan välinen etäisyys on nyt $3$, joten 1. kilpailija siirtyy koordinaattiin $3$. 1., 2. ja 3. kilpailija seisovat koordinaateissa $3$, $-2$ ja $-3$. Koska välillä $[2,4]$ ovat IOI-chan ja 1. kilpailija, tulosta 2 4. kysymykseen.
• Ajanhetkellä $5$ IOI-chan siirtyy koordinaattiin $5$. Kukaan kilpailijoista ei liiku; 1., 2. ja 3. kilpailija seisovat koordinaateissa $3$, $-2$ ja $-3$. Koska välillä $[2,4]$ on vain 1. kilpailija, tulosta 1 5. kysymykseen.
• Ajanhetkellä $6$ IOI-chan siirtyy koordinaattiin $6$. IOI-chanin ja 1. kilpailijan välinen etäisyys on nyt $3$, joten 1. kilpailija siirtyy koordinaattiin $5$. Tällöin 1. ja 2. kilpailijan välinen etäisyys on nyt $7$, joten 2. kilpailija siirtyy koordinaattiin $4$. Lisäksi 2. ja 3. kilpailijan välinen etäisyys on nyt $7$, joten 3. kilpailija siirtyy koordinaattiin $3$. 1., 2. ja 3. kilpailija seisovat koordinaateissa $5$, $4$ ja $3$. Koska välillä $[2,4]$ ovat 2. ja 3. kilpailija, tulosta 2 6. kysymykseen.

Syöte 2

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

Tuloste 2

2
0

Huomautus

Tämä esimerkkisyöte täyttää osatehtävän 1 rajoitukset.

Syöte 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

Tuloste 3

1
6
0
5
2
7