Pada upacara pembukaan IOI 2018, $N$ peserta berbaris di sepanjang suatu garis yang direpresentasikan oleh garis bilangan. Semua peserta menghadap ke arah positif garis bilangan. Pada waktu $0$, peserta ke-$i$ ($1 \le i \le N$, dihitung dari depan) berada pada koordinat $-i$. Selain itu, IOI-chan, sang pembawa bendera, berada pada koordinat $0$.

Setiap peserta memiliki nilai yang disebut kelambanan. Peserta ke-$i$ memiliki kelambanan $D_i$. Para peserta mengikuti aturan berikut:

• Jika jarak peserta ke-$i$ dari orang (peserta atau IOI-chan) tepat di depannya setidaknya $D_i+1$, peserta ke-$i$ bergerak ke posisi yang berjarak $1$ dari orang tersebut. Jika tidak, peserta ke-$i$ tidak bergerak.

IOI-chan bergerak sejauh $1$ ke arah positif garis bilangan per satuan waktu. Seorang peserta bergerak seketika setiap kali kondisi di atas terpenuhi.

Anda adalah seorang reporter yang meliput upacara pembukaan. Anda seharusnya mengambil foto, tetapi Anda tertidur lelap selama seluruh upacara. Apa boleh buat—Anda memutuskan untuk berbuat curang dengan mengambil foto tempat acara lalu menggambar orang-orang di atasnya.

Agar kecurangan Anda tidak ketahuan, atau untuk memperkirakan waktu yang diperlukan untuk menggambar, Anda ingin mengetahui $Q$ nilai berikut:

• Banyaknya orang yang berada pada koordinat antara $L_j$ dan $R_j$, inklusif, pada waktu $T_j$ ($1 \le j \le Q$).

Tugas

Diberikan kelambanan setiap peserta dan data $Q$ pertanyaan, tulislah program yang menghitung banyaknya orang yang memenuhi kondisi untuk setiap pertanyaan.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama masukan berisi dua bilangan bulat $N$ dan $Q$ yang dipisahkan oleh spasi. Artinya, terdapat $N$ peserta (tidak termasuk IOI-chan) dan $Q$ pertanyaan.
• Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi sebuah bilangan bulat $D_i$. Artinya, peserta ke-$i$ dari depan memiliki kelambanan $D_i$.
• Baris ke-$j$ ($1 \le j \le Q$) dari $Q$ baris berikutnya berisi tiga bilangan bulat $T_j$, $L_j$, dan $R_j$ yang dipisahkan oleh spasi. Nilai-nilai ini menyatakan pertanyaan ke-$j$.

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Baris ke-$j$ ($1 \le j \le Q$) keluaran harus berisi jawaban untuk pertanyaan ke-$j$.

Batasan

Semua data masukan memenuhi kondisi berikut.

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

Subsoal

Terdapat 3 subsoal. Skor dan batasan tambahan setiap subsoal adalah sebagai berikut:

Subsoal 1 [7 poin]

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

Subsoal 2 [12 poin]

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

Subsoal 3 [81 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

0
1
1
2
1
2

Penjelasan

Pada contoh masukan ini, para peserta dan IOI-chan bergerak sebagai berikut.

Dalam penjelasan berikut, interval $[L,R]$ menyatakan himpunan titik pada garis bilangan dengan koordinat antara $L$ dan $R$, inklusif.

• Pada waktu $0$, IOI-chan berada pada koordinat $0$. Peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $-1$, $-2$, dan $-3$.
• Pada waktu $1$, IOI-chan bergerak ke koordinat $1$. Tidak ada peserta yang bergerak; peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $-1$, $-2$, dan $-3$. Karena tidak ada orang dalam interval $[2,4]$, keluarkan 0 untuk pertanyaan pertama.
• Pada waktu $2$, IOI-chan bergerak ke koordinat $2$. Jarak antara IOI-chan dan peserta pertama kini $3$, sehingga peserta pertama bergerak ke koordinat $1$. Peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $1$, $-2$, dan $-3$. Karena hanya IOI-chan yang berada dalam interval $[2,4]$, keluarkan 1 untuk pertanyaan kedua.
• Pada waktu $3$, IOI-chan bergerak ke koordinat $3$. Tidak ada peserta yang bergerak; peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $1$, $-2$, dan $-3$. Karena hanya IOI-chan yang berada dalam interval $[2,4]$, keluarkan 1 untuk pertanyaan ketiga.
• Pada waktu $4$, IOI-chan bergerak ke koordinat $4$. Jarak antara IOI-chan dan peserta pertama kini $3$, sehingga peserta pertama bergerak ke koordinat $3$. Peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $3$, $-2$, dan $-3$. Karena IOI-chan dan peserta pertama berada dalam interval $[2,4]$, keluarkan 2 untuk pertanyaan keempat.
• Pada waktu $5$, IOI-chan bergerak ke koordinat $5$. Tidak ada peserta yang bergerak; peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $3$, $-2$, dan $-3$. Karena hanya peserta pertama yang berada dalam interval $[2,4]$, keluarkan 1 untuk pertanyaan kelima.
• Pada waktu $6$, IOI-chan bergerak ke koordinat $6$. Jarak antara IOI-chan dan peserta pertama kini $3$, sehingga peserta pertama bergerak ke koordinat $5$. Kemudian, jarak antara peserta pertama dan kedua kini $7$, sehingga peserta kedua bergerak ke koordinat $4$. Selanjutnya, jarak antara peserta kedua dan ketiga kini $7$, sehingga peserta ketiga bergerak ke koordinat $3$. Peserta pertama, kedua, dan ketiga masing-masing berada pada koordinat $5$, $4$, dan $3$. Karena peserta kedua dan ketiga berada dalam interval $[2,4]$, keluarkan 2 untuk pertanyaan keenam.

Masukan 2

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

Keluaran 2

2
0

Penjelasan

Contoh masukan ini memenuhi batasan subsoal 1.

Masukan 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

Keluaran 3

1
6
0
5
2
7