Podczas ceremonii otwarcia IOI 2018 $N$ zawodników maszeruje wzdłuż prostej przedstawionej jako oś liczbowa. Wszyscy zawodnicy zmierzają w dodatnim kierunku osi. W chwili $0$ zawodnik numer $i$ ($1 \le i \le N$, licząc od przodu) stoi we współrzędnej $-i$. Ponadto IOI-chan, niosąca flagę, stoi we współrzędnej $0$.

Każdy zawodnik ma wartość nazywaną powolnością. Powolność zawodnika numer $i$ wynosi $D_i$. Zawodnicy przestrzegają następującej zasady:

• Jeśli odległość zawodnika numer $i$ od osoby (zawodnika lub IOI-chan) znajdującej się bezpośrednio przed nim jest większa lub równa $D_i+1$, zawodnik numer $i$ przemieszcza się do pozycji w odległości $1$ od tej osoby. W przeciwnym razie zawodnik numer $i$ się nie porusza.

IOI-chan przemieszcza się o odległość $1$ w dodatnim kierunku osi w każdej jednostce czasu. Zawodnik przemieszcza się natychmiast, gdy tylko opisany powyżej warunek jest spełniony.

Jesteś reporterem relacjonującym ceremonię otwarcia. Miałeś robić zdjęcia, ale przespałeś całą ceremonię. Nie było rady — postanowiłeś oszukać, robiąc zdjęcia sali, a następnie dorysowując na nich ludzi.

Aby twoje oszustwo nie zostało wykryte lub aby oszacować czas potrzebny na dorysowanie ludzi, chcesz poznać następujące $Q$ wartości:

• liczbę osób stojących we współrzędnych od $L_j$ do $R_j$ włącznie w chwili $T_j$ ($1 \le j \le Q$).

Zadanie

Mając dane powolności wszystkich zawodników oraz dane $Q$ zapytań, napisz program obliczający dla każdego zapytania liczbę osób spełniających podany warunek.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz wejścia zawiera dwie liczby całkowite $N$ i $Q$ oddzielone spacją. Oznacza to, że jest $N$ zawodników (nie licząc IOI-chan) oraz $Q$ zapytań.
• Wiersz numer $i$ ($1 \le i \le N$) z kolejnych $N$ wierszy zawiera liczbę całkowitą $D_i$. Oznacza ona, że zawodnik numer $i$, licząc od przodu, ma powolność $D_i$.
• Wiersz numer $j$ ($1 \le j \le Q$) z kolejnych $Q$ wierszy zawiera trzy liczby całkowite $T_j$, $L_j$ i $R_j$ oddzielone spacjami. Wartości te opisują zapytanie numer $j$.

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. Wiersz numer $j$ ($1 \le j \le Q$) powinien zawierać odpowiedź na zapytanie numer $j$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

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

Podzadania

Są 3 podzadania. Punktacja oraz dodatkowe ograniczenia dla każdego podzadania są następujące:

Podzadanie 1 [7 punktów]

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

Podzadanie 2 [12 punktów]

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

Podzadanie 3 [81 punktów]

Nie ma dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

0
1
1
2
1
2

Uwagi

W tym przykładzie zawodnicy oraz IOI-chan poruszają się następująco.

W poniższym opisie przedział $[L,R]$ oznacza zbiór punktów o współrzędnych od $L$ do $R$ włącznie na osi liczbowej.

• W chwili $0$ IOI-chan stoi we współrzędnej $0$. Pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $-1$, $-2$ i $-3$.
• W chwili $1$ IOI-chan przemieszcza się do współrzędnej $1$. Żaden zawodnik się nie porusza; pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $-1$, $-2$ i $-3$. Ponieważ w przedziale $[2,4]$ nie ma żadnej osoby, odpowiedź na pierwsze zapytanie to $0$.
• W chwili $2$ IOI-chan przemieszcza się do współrzędnej $2$. Odległość między IOI-chan a pierwszym zawodnikiem wynosi teraz $3$, więc pierwszy zawodnik przemieszcza się do współrzędnej $1$. Pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $1$, $-2$ i $-3$. Ponieważ w przedziale $[2,4]$ znajduje się tylko IOI-chan, odpowiedź na drugie zapytanie to $1$.
• W chwili $3$ IOI-chan przemieszcza się do współrzędnej $3$. Żaden zawodnik się nie porusza; pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $1$, $-2$ i $-3$. Ponieważ w przedziale $[2,4]$ znajduje się tylko IOI-chan, odpowiedź na trzecie zapytanie to $1$.
• W chwili $4$ IOI-chan przemieszcza się do współrzędnej $4$. Odległość między IOI-chan a pierwszym zawodnikiem wynosi teraz $3$, więc pierwszy zawodnik przemieszcza się do współrzędnej $3$. Pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $3$, $-2$ i $-3$. Ponieważ w przedziale $[2,4]$ znajdują się IOI-chan oraz pierwszy zawodnik, odpowiedź na czwarte zapytanie to $2$.
• W chwili $5$ IOI-chan przemieszcza się do współrzędnej $5$. Żaden zawodnik się nie porusza; pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $3$, $-2$ i $-3$. Ponieważ w przedziale $[2,4]$ znajduje się tylko pierwszy zawodnik, odpowiedź na piąte zapytanie to $1$.
• W chwili $6$ IOI-chan przemieszcza się do współrzędnej $6$. Odległość między IOI-chan a pierwszym zawodnikiem wynosi teraz $3$, więc pierwszy zawodnik przemieszcza się do współrzędnej $5$. Wtedy odległość między pierwszym a drugim zawodnikiem wynosi $7$, więc drugi zawodnik przemieszcza się do współrzędnej $4$. Ponadto odległość między drugim a trzecim zawodnikiem wynosi teraz $7$, więc trzeci zawodnik przemieszcza się do współrzędnej $3$. Pierwszy, drugi i trzeci zawodnik stoją odpowiednio we współrzędnych $5$, $4$ i $3$. Ponieważ w przedziale $[2,4]$ znajdują się drugi i trzeci zawodnik, odpowiedź na szóste zapytanie to $2$.

Wejście 2

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

Wyjście 2

2
0

Uwagi

Ten przykład spełnia ograniczenia podzadania 1.

Wejście 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

Wyjście 3

1
6
0
5
2
7