На церемонії відкриття IOI 2018 $N$ учасників крокують уздовж прямої, яку подано числовою віссю. Усі учасники рухаються в додатному напрямку числової осі. У момент часу $0$ учасник з номером $i$ ($1 \le i \le N$, рахуючи від початку колони) стоїть у точці з координатою $-i$. Крім того, прапороносиця IOI-chan стоїть у точці з координатою $0$.

Кожен учасник має величину, що називається повільністю. Повільність $i$-го учасника дорівнює $D_i$. Учасники дотримуються такого правила:

• Якщо відстань від $i$-го учасника до людини (учасника або IOI-chan), яка стоїть безпосередньо перед ним, більша або дорівнює $D_i+1$, то $i$-й учасник переходить у позицію на відстані $1$ від цієї людини. Інакше $i$-й учасник не рухається.

IOI-chan за одиницю часу проходить відстань $1$ у додатному напрямку осі. Учасник переміщується миттєво щоразу, коли виконується описана вище умова.

Ви — репортер, який висвітлює церемонію відкриття. Ви мали фотографувати, але міцно проспали всю церемонію. Нічого не вдієш — ви вирішили схитрувати: сфотографувати зал, а потім домалювати на фотографіях людей.

Щоб вас не викрили або щоб оцінити час, потрібний для малювання, ви хочете дізнатися такі $Q$ значень:

• кількість людей, які в момент часу $T_j$ стоять у точках із координатами від $L_j$ до $R_j$ включно ($1 \le j \le Q$).

Завдання

За повільністю кожного учасника та даними $Q$ запитів напишіть програму, яка для кожного запиту обчислює кількість людей, що задовольняють умову.

Вхідні дані

Прочитайте такі дані зі стандартного вводу.

• Перший рядок містить два цілі числа $N$ і $Q$, розділені пробілом. Це означає, що є $N$ учасників (не враховуючи IOI-chan) і $Q$ запитів.
• $i$-й рядок ($1 \le i \le N$) із наступних $N$ рядків містить ціле число $D_i$. Це означає, що повільність $i$-го учасника від початку колони дорівнює $D_i$.
• $j$-й рядок ($1 \le j \le Q$) із наступних $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-chan рухаються так.

Далі відрізок $[L,R]$ позначає множину точок числової осі з координатами від $L$ до $R$ включно.

• У момент часу $0$ IOI-chan стоїть у точці з координатою $0$. Перший, другий і третій учасники стоять у точках із координатами $-1$, $-2$ і $-3$ відповідно.
• У момент часу $1$ IOI-chan переходить у точку з координатою $1$. Жоден учасник не рухається; перший, другий і третій учасники стоять у точках із координатами $-1$, $-2$ і $-3$ відповідно. Оскільки на відрізку $[2,4]$ немає людей, для першого запиту виведіть 0.
• У момент часу $2$ IOI-chan переходить у точку з координатою $2$. Відстань між IOI-chan і першим учасником тепер дорівнює $3$, тому перший учасник переходить у точку з координатою $1$. Перший, другий і третій учасники стоять у точках із координатами $1$, $-2$ і $-3$ відповідно. Оскільки на відрізку $[2,4]$ є лише IOI-chan, для другого запиту виведіть 1.
• У момент часу $3$ IOI-chan переходить у точку з координатою $3$. Жоден учасник не рухається; перший, другий і третій учасники стоять у точках із координатами $1$, $-2$ і $-3$ відповідно. Оскільки на відрізку $[2,4]$ є лише IOI-chan, для третього запиту виведіть 1.
• У момент часу $4$ IOI-chan переходить у точку з координатою $4$. Відстань між IOI-chan і першим учасником тепер дорівнює $3$, тому перший учасник переходить у точку з координатою $3$. Перший, другий і третій учасники стоять у точках із координатами $3$, $-2$ і $-3$ відповідно. Оскільки на відрізку $[2,4]$ є IOI-chan і перший учасник, для четвертого запиту виведіть 2.
• У момент часу $5$ IOI-chan переходить у точку з координатою $5$. Жоден учасник не рухається; перший, другий і третій учасники стоять у точках із координатами $3$, $-2$ і $-3$ відповідно. Оскільки на відрізку $[2,4]$ є лише перший учасник, для п'ятого запиту виведіть 1.
• У момент часу $6$ IOI-chan переходить у точку з координатою $6$. Відстань між IOI-chan і першим учасником тепер дорівнює $3$, тому перший учасник переходить у точку з координатою $5$. Тоді відстань між першим і другим учасниками стає рівною $7$, тому другий учасник переходить у точку з координатою $4$. Крім того, відстань між другим і третім учасниками тепер дорівнює $7$, тому третій учасник переходить у точку з координатою $3$. Перший, другий і третій учасники стоять у точках із координатами $5$, $4$ і $3$ відповідно. Оскільки на відрізку $[2,4]$ є другий і третій учасники, для шостого запиту виведіть 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