На церемонии открытия 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