IOI 2018 ашылу салтанатында $N$ қатысушы сан осімен сипатталатын түзу бойымен сап түзеп жүреді. Барлық қатысушылар сан осінің оң бағытына қарай бет алады. $0$ уақыт мезетінде $i$-ші қатысушы ($1 \le i \le N$, алдынан бастап санағанда) $-i$ координатасында тұрады. Сонымен қатар, ту ұстаушы IOI-тян $0$ координатасында тұрады.

Әрбір қатысушының баяулық деп аталатын мәні бар. $i$-ші қатысушының баяулығы — $D_i$. Қатысушылар келесі ережені ұстанады:

• Егер $i$-ші қатысушы өзінің дәл алдында тұрған адамнан (қатысушыдан немесе IOI-тяннан) $D_i+1$ немесе одан үлкен қашықтықта болса, $i$-ші қатысушы сол адамнан $1$ қашықтықтағы орынға жылжиды. Әйтпесе, $i$-ші қатысушы қозғалмайды.

IOI-тян уақыт бірлігінде түзу бойымен оң бағытта $1$ қашықтыққа жылжиды. Қатысушы жоғарыда сипатталған шарт орындалған сайын лезде жылжиды.

Сіз ашылу салтанатын жариялайтын тілшісіз. Сіз фотосуреттер түсіруіңіз керек еді, бірақ бүкіл салтанат бойы қатты ұйықтап қалдыңыз. Амал жоқ — сіз залды суретке түсіріп, содан кейін олардың үстіне адамдардың суреттерін салып, қулық жасауды ұйғардыңыз.

Қулығыңыз әшкере болмауы үшін немесе сурет салу уақытын бағалау үшін сіз келесі $Q$ мәнді білгіңіз келеді:

• $T_j$ уақыт мезетінде координатасы $L_j$ мен $R_j$ аралығында (шеткі нүктелерді қоса алғанда) тұрған адамдар саны ($1 \le j \le Q$).

Тапсырма

Әрбір қатысушының баяулығы және $Q$ сұрақтың деректері берілгенде, әрбір сұрақ үшін шартты қанағаттандыратын адамдар санын есептейтін программа жазыңыз.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз.

• Кірістің бірінші жолында бос орынмен бөлінген екі бүтін сан $N$ және $Q$ берілген. Бұл $N$ қатысушы (IOI-тянды қоспағанда) және $Q$ сұрақ бар екенін білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бүтін сан $D_i$ берілген. Бұл алдынан санағанда $i$-ші қатысушының баяулығы $D_i$ екенін білдіреді.
• Келесі $Q$ жолдың $j$-ші жолында ($1 \le j \le Q$) бос орынмен бөлінген үш бүтін сан $T_j$, $L_j$ және $R_j$ берілген. Бұл мәндер $j$-ші сұрақты білдіреді.

Шығыс деректер

Стандартты шығысқа $Q$ жол жазыңыз. Шығыстың $j$-ші жолында ($1 \le j \le Q$) $j$-ші сұрақтың жауабы болуы тиіс.

Шектеулер

Барлық кіріс деректері келесі шарттарды қанағаттандырады.

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

Ішкі есептер

3 ішкі есеп бар. Әрбір ішкі есептің ұпайы мен қосымша шектеулері келесідей:

Ішкі есеп 1 [7 ұпай]

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

Ішкі есеп 2 [12 ұпай]

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

Ішкі есеп 3 [81 ұпай]

Қосымша шектеулер жоқ.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

0
1
1
2
1
2

Ескертпе

Бұл мысалда қатысушылар мен IOI-тян келесідей қозғалады.

Төменде $[L,R]$ аралығы сан осіндегі координатасы $L$ мен $R$ арасындағы (шеткі нүктелерді қоса алғанда) нүктелер жиынын білдіреді.

• $0$ уақыт мезетінде IOI-тян $0$ координатасында тұрады. 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $-1$, $-2$ және $-3$ координаталарында тұрады.
• $1$ уақыт мезетінде IOI-тян $1$ координатасына жылжиды. Ешбір қатысушы қозғалмайды; 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $-1$, $-2$ және $-3$ координаталарында тұрады. $[2,4]$ аралығында ешкім жоқ болғандықтан, 1-ші сұраққа 0 шығарылады.
• $2$ уақыт мезетінде IOI-тян $2$ координатасына жылжиды. IOI-тян мен 1-ші қатысушының арақашықтығы енді $3$ болғандықтан, 1-ші қатысушы $1$ координатасына жылжиды. 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $1$, $-2$ және $-3$ координаталарында тұрады. $[2,4]$ аралығында тек IOI-тян бар болғандықтан, 2-ші сұраққа 1 шығарылады.
• $3$ уақыт мезетінде IOI-тян $3$ координатасына жылжиды. Ешбір қатысушы қозғалмайды; 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $1$, $-2$ және $-3$ координаталарында тұрады. $[2,4]$ аралығында тек IOI-тян бар болғандықтан, 3-ші сұраққа 1 шығарылады.
• $4$ уақыт мезетінде IOI-тян $4$ координатасына жылжиды. IOI-тян мен 1-ші қатысушының арақашықтығы енді $3$ болғандықтан, 1-ші қатысушы $3$ координатасына жылжиды. 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $3$, $-2$ және $-3$ координаталарында тұрады. $[2,4]$ аралығында IOI-тян мен 1-ші қатысушы бар болғандықтан, 4-ші сұраққа 2 шығарылады.
• $5$ уақыт мезетінде IOI-тян $5$ координатасына жылжиды. Ешбір қатысушы қозғалмайды; 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $3$, $-2$ және $-3$ координаталарында тұрады. $[2,4]$ аралығында тек 1-ші қатысушы бар болғандықтан, 5-ші сұраққа 1 шығарылады.
• $6$ уақыт мезетінде IOI-тян $6$ координатасына жылжиды. IOI-тян мен 1-ші қатысушының арақашықтығы енді $3$ болғандықтан, 1-ші қатысушы $5$ координатасына жылжиды. Содан кейін 1-ші және 2-ші қатысушылардың арақашықтығы енді $7$ болғандықтан, 2-ші қатысушы $4$ координатасына жылжиды. Одан әрі 2-ші және 3-ші қатысушылардың арақашықтығы енді $7$ болғандықтан, 3-ші қатысушы $3$ координатасына жылжиды. 1-ші, 2-ші және 3-ші қатысушылар сәйкесінше $5$, $4$ және $3$ координаталарында тұрады. $[2,4]$ аралығында 2-ші және 3-ші қатысушылар бар болғандықтан, 6-шы сұраққа 2 шығарылады.

Кіріс деректер 2

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

Шығыс деректер 2

2
0

Ескертпе

Бұл кіріс мысалы 1-ші ішкі есептің шектеулерін қанағаттандырады.

Кіріс деректер 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

Шығыс деректер 3

1
6
0
5
2
7