Na cerimônia de abertura da IOI 2018, $N$ competidores marcham em fila, representada por uma reta numérica. Todos seguem no sentido positivo da reta. No instante $0$, o $i$-ésimo competidor ($1 \le i \le N$, contado a partir da frente) está na coordenada $-i$. Além disso, IOI-chan, que carrega a bandeira, está na coordenada $0$.

Cada competidor tem um valor chamado lentidão. O $i$-ésimo competidor tem lentidão $D_i$. Os competidores seguem a seguinte regra:

• Se o $i$-ésimo competidor estiver a uma distância maior ou igual a $D_i+1$ da pessoa (um competidor ou IOI-chan) imediatamente à sua frente, ele se move para a posição a uma distância de $1$ dessa pessoa. Caso contrário, o $i$-ésimo competidor não se move.

IOI-chan percorre uma distância de $1$ no sentido positivo da reta por unidade de tempo. Um competidor se move instantaneamente sempre que a condição acima é satisfeita.

Você é um repórter encarregado de cobrir a cerimônia de abertura. Deveria tirar fotos, mas dormiu profundamente durante toda a cerimônia. Não havia o que fazer: você decidiu trapacear, fotografando o salão e depois desenhando as pessoas nas fotos.

Para não ser descoberto, ou para estimar o tempo necessário para desenhar, você quer saber os seguintes $Q$ valores:

• O número de pessoas que estão em coordenadas entre $L_j$ e $R_j$, inclusive, no instante $T_j$ ($1 \le j \le Q$).

Tarefa

Dadas a lentidão de cada competidor e as informações das $Q$ perguntas, escreva um programa que calcule, para cada pergunta, o número de pessoas que satisfazem a condição.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém dois inteiros $N$ e $Q$, separados por um espaço. Isso significa que há $N$ competidores (sem incluir IOI-chan) e $Q$ perguntas.
• A $i$-ésima linha ($1 \le i \le N$) das próximas $N$ linhas contém um inteiro $D_i$. Isso significa que o $i$-ésimo competidor a partir da frente tem lentidão $D_i$.
• A $j$-ésima linha ($1 \le j \le Q$) das próximas $Q$ linhas contém três inteiros $T_j$, $L_j$ e $R_j$, separados por espaços. Esses valores representam a $j$-ésima pergunta.

Saída

Escreva $Q$ linhas na saída padrão. A $j$-ésima linha ($1 \le j \le Q$) deve conter a resposta à $j$-ésima pergunta.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Há 3 subtarefas. A pontuação e as restrições adicionais de cada uma são as seguintes:

Subtarefa 1 [7 pontos]

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

Subtarefa 2 [12 pontos]

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

Subtarefa 3 [81 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

0
1
1
2
1
2

Explicação

Neste exemplo, os competidores e IOI-chan se movem da seguinte maneira.

A seguir, o intervalo $[L,R]$ denota o conjunto dos pontos da reta numérica com coordenadas entre $L$ e $R$, inclusive.

• No instante $0$, IOI-chan está na coordenada $0$. O 1º, o 2º e o 3º competidores estão nas coordenadas $-1$, $-2$ e $-3$, respectivamente.
• No instante $1$, IOI-chan se move para a coordenada $1$. Nenhum competidor se move; o 1º, o 2º e o 3º competidores estão nas coordenadas $-1$, $-2$ e $-3$, respectivamente. Como não há pessoas no intervalo $[2,4]$, a resposta à 1ª pergunta é $0$.
• No instante $2$, IOI-chan se move para a coordenada $2$. A distância entre IOI-chan e o 1º competidor agora é $3$, então o 1º competidor se move para a coordenada $1$. O 1º, o 2º e o 3º competidores estão nas coordenadas $1$, $-2$ e $-3$, respectivamente. Como apenas IOI-chan está no intervalo $[2,4]$, a resposta à 2ª pergunta é $1$.
• No instante $3$, IOI-chan se move para a coordenada $3$. Nenhum competidor se move; o 1º, o 2º e o 3º competidores estão nas coordenadas $1$, $-2$ e $-3$, respectivamente. Como apenas IOI-chan está no intervalo $[2,4]$, a resposta à 3ª pergunta é $1$.
• No instante $4$, IOI-chan se move para a coordenada $4$. A distância entre IOI-chan e o 1º competidor agora é $3$, então o 1º competidor se move para a coordenada $3$. O 1º, o 2º e o 3º competidores estão nas coordenadas $3$, $-2$ e $-3$, respectivamente. Como IOI-chan e o 1º competidor estão no intervalo $[2,4]$, a resposta à 4ª pergunta é $2$.
• No instante $5$, IOI-chan se move para a coordenada $5$. Nenhum competidor se move; o 1º, o 2º e o 3º competidores estão nas coordenadas $3$, $-2$ e $-3$, respectivamente. Como apenas o 1º competidor está no intervalo $[2,4]$, a resposta à 5ª pergunta é $1$.
• No instante $6$, IOI-chan se move para a coordenada $6$. A distância entre IOI-chan e o 1º competidor agora é $3$, então o 1º competidor se move para a coordenada $5$. Em seguida, a distância entre o 1º e o 2º competidores passa a ser $7$, então o 2º competidor se move para a coordenada $4$. Além disso, a distância entre o 2º e o 3º competidores passa a ser $7$, então o 3º competidor se move para a coordenada $3$. O 1º, o 2º e o 3º competidores estão nas coordenadas $5$, $4$ e $3$, respectivamente. Como o 2º e o 3º competidores estão no intervalo $[2,4]$, a resposta à 6ª pergunta é $2$.

Entrada 2

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

Saída 2

2
0

Explicação

Este exemplo satisfaz as restrições da subtarefa 1.

Entrada 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

Saída 3

1
6
0
5
2
7