Alla cerimonia di apertura delle IOI 2018, $N$ concorrenti marciano lungo una linea, che è rappresentata da una retta numerica. Tutti i concorrenti si dirigono verso la direzione positiva della retta numerica. Al tempo $0$, l'$i$-esimo concorrente ($1 \le i \le N$, contando dalla testa) si trova alla coordinata $-i$. Inoltre, IOI-chan, la portabandiera, si trova alla coordinata $0$.

Ogni concorrente ha un valore chiamato lentezza. L'$i$-esimo concorrente ha lentezza $D_i$. I concorrenti rispettano la seguente regola:

• Se l'$i$-esimo concorrente si trova a una distanza maggiore o uguale a $D_i+1$ dalla persona (un concorrente o IOI-chan) che si trova immediatamente davanti a lui o lei, l'$i$-esimo concorrente si sposta nella posizione a distanza $1$ da quella persona. Altrimenti, l'$i$-esimo concorrente non si muove.

IOI-chan si muove di una distanza $1$ nella direzione positiva sulla retta per unità di tempo. Un concorrente si muove istantaneamente ogni volta che la condizione descritta sopra è soddisfatta.

Sei un reporter incaricato di seguire la cerimonia di apertura. Dovevi scattare delle foto, ma hai dormito profondamente durante tutta la cerimonia. Non potendo farci nulla, hai deciso di imbrogliare scattando foto della sala e poi disegnandoci sopra le immagini delle persone.

Per non farti scoprire a imbrogliare, o per stimare il tempo necessario a disegnare le immagini, vuoi conoscere i seguenti $Q$ valori:

• il numero di persone che si trovano a una coordinata compresa tra $L_j$ e $R_j$, estremi inclusi, al tempo $T_j$ ($1 \le j \le Q$).

Compito

Data la lentezza di ciascun concorrente e i dati delle $Q$ domande, scrivi un programma che calcoli il numero di persone che soddisfano la condizione per ciascuna domanda.

Input

Leggi i seguenti dati dallo standard input.

• La prima riga dell'input contiene due interi separati da spazio $N$ e $Q$. Ciò significa che ci sono $N$ concorrenti (esclusa IOI-chan) e ci sono $Q$ domande.
• La $i$-esima riga ($1 \le i \le N$) delle successive $N$ righe contiene un intero $D_i$. Ciò significa che l'$i$-esimo concorrente dalla testa ha lentezza $D_i$.
• La $j$-esima riga ($1 \le j \le Q$) delle successive $Q$ righe contiene tre interi separati da spazio $T_j$, $L_j$ e $R_j$. Questi valori rappresentano la $j$-esima domanda.

Output

Scrivi $Q$ righe sullo standard output. La $j$-esima riga ($1 \le j \le Q$) dell'output deve contenere la risposta alla $j$-esima domanda.

Limiti

Tutti i dati di input soddisfano le seguenti condizioni.

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

Sottoproblemi

Ci sono 3 sottoproblemi. Il punteggio e i limiti aggiuntivi di ciascun sottoproblema sono i seguenti:

Sottoproblema 1 [7 punti]

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

Sottoproblema 2 [12 punti]

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

Sottoproblema 3 [81 punti]

Non ci sono limitazioni aggiuntive.

Esempi

Input 1

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

Output 1

0
1
1
2
1
2

Note

In questo esempio di input, i concorrenti e IOI-chan si muovono come segue.

Nel seguito, l'intervallo $[L,R]$ indica l'insieme dei punti di coordinata compresa tra $L$ e $R$, estremi inclusi, sulla retta numerica.

• Al tempo $0$, IOI-chan si trova alla coordinata $0$. Il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $-1$, $-2$ e $-3$.
• Al tempo $1$, IOI-chan si sposta alla coordinata $1$. Nessun concorrente si muove; il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $-1$, $-2$ e $-3$. Poiché non ci sono persone nell'intervallo $[2,4]$, stampa 0 per la 1ª domanda.
• Al tempo $2$, IOI-chan si sposta alla coordinata $2$. La distanza tra IOI-chan e il 1° concorrente è ora $3$, quindi il 1° concorrente si sposta alla coordinata $1$. Il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $1$, $-2$ e $-3$. Poiché c'è solo IOI-chan nell'intervallo $[2,4]$, stampa 1 per la 2ª domanda.
• Al tempo $3$, IOI-chan si sposta alla coordinata $3$. Nessun concorrente si muove; il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $1$, $-2$ e $-3$. Poiché c'è solo IOI-chan nell'intervallo $[2,4]$, stampa 1 per la 3ª domanda.
• Al tempo $4$, IOI-chan si sposta alla coordinata $4$. La distanza tra IOI-chan e il 1° concorrente è ora $3$, quindi il 1° concorrente si sposta alla coordinata $3$. Il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $3$, $-2$ e $-3$. Poiché ci sono IOI-chan e il 1° concorrente nell'intervallo $[2,4]$, stampa 2 per la 4ª domanda.
• Al tempo $5$, IOI-chan si sposta alla coordinata $5$. Nessun concorrente si muove; il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $3$, $-2$ e $-3$. Poiché c'è solo il 1° concorrente nell'intervallo $[2,4]$, stampa 1 per la 5ª domanda.
• Al tempo $6$, IOI-chan si sposta alla coordinata $6$. La distanza tra IOI-chan e il 1° concorrente è ora $3$, quindi il 1° concorrente si sposta alla coordinata $5$. Poi, la distanza tra il 1° e il 2° concorrente è ora $7$, quindi il 2° concorrente si sposta alla coordinata $4$. Inoltre, la distanza tra il 2° e il 3° concorrente è ora $7$, quindi il 3° concorrente si sposta alla coordinata $3$. Il 1°, 2° e 3° concorrente si trovano rispettivamente alle coordinate $5$, $4$ e $3$. Poiché ci sono il 2° e il 3° concorrente nell'intervallo $[2,4]$, stampa 2 per la 6ª domanda.

Input 2

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

Output 2

2
0

Note

Questo esempio di input soddisfa i limiti del sottoproblema 1.

Input 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

Output 3

1
6
0
5
2
7