Trong lễ khai mạc IOI 2018, $N$ thí sinh diễu hành theo một hàng, được biểu diễn bằng một trục số. Tất cả thí sinh đều đi về chiều dương của trục số. Tại thời điểm $0$, thí sinh thứ $i$ ($1 \le i \le N$, tính từ đầu hàng) đứng tại tọa độ $-i$. Ngoài ra, IOI-chan, người cầm cờ, đứng tại tọa độ $0$.

Mỗi thí sinh có một giá trị gọi là độ chậm chạp. Thí sinh thứ $i$ có độ chậm chạp $D_i$. Các thí sinh tuân theo quy tắc sau:

• Nếu khoảng cách từ thí sinh thứ $i$ đến người (một thí sinh hoặc IOI-chan) ngay phía trước mình lớn hơn hoặc bằng $D_i+1$, thí sinh thứ $i$ di chuyển đến vị trí cách người đó một khoảng bằng $1$. Ngược lại, thí sinh thứ $i$ không di chuyển.

IOI-chan di chuyển một khoảng bằng $1$ theo chiều dương của trục số trong mỗi đơn vị thời gian. Một thí sinh di chuyển tức thời ngay khi điều kiện nêu trên được thỏa mãn.

Bạn là phóng viên đưa tin về lễ khai mạc. Bạn đáng lẽ phải chụp ảnh, nhưng lại ngủ say suốt buổi lễ. Không còn cách nào khác, bạn quyết định gian lận bằng cách chụp ảnh hội trường rồi vẽ thêm hình người lên các bức ảnh đó.

Để không bị phát hiện gian lận, hoặc để ước tính thời gian cần thiết để vẽ, bạn muốn biết $Q$ giá trị sau:

• Số người đứng tại các tọa độ từ $L_j$ đến $R_j$, kể cả hai đầu mút, tại thời điểm $T_j$ ($1 \le j \le Q$).

Nhiệm vụ

Cho độ chậm chạp của từng thí sinh và dữ liệu của $Q$ câu hỏi, hãy viết chương trình tính số người thỏa mãn điều kiện của mỗi câu hỏi.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên $N$ và $Q$, cách nhau một dấu cách. Điều này có nghĩa là có $N$ thí sinh (không bao gồm IOI-chan) và có $Q$ câu hỏi.
• Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo chứa một số nguyên $D_i$. Điều này có nghĩa là thí sinh thứ $i$ tính từ đầu hàng có độ chậm chạp $D_i$.
• Dòng thứ $j$ ($1 \le j \le Q$) trong $Q$ dòng tiếp theo chứa ba số nguyên $T_j$, $L_j$ và $R_j$, cách nhau bởi dấu cách. Các giá trị này biểu diễn câu hỏi thứ $j$.

Dữ liệu ra

Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1 \le j \le Q$) phải chứa đáp án cho câu hỏi thứ $j$.

Giới hạn

Tất cả dữ liệu đầu vào thỏa mãn các điều kiện sau.

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

Nhiệm vụ con

Có 3 nhiệm vụ con. Điểm số và các giới hạn bổ sung của mỗi nhiệm vụ con như sau:

Nhiệm vụ con 1 [7 điểm]

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

Nhiệm vụ con 2 [12 điểm]

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

Nhiệm vụ con 3 [81 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0
1
1
2
1
2

Ghi chú

Trong ví dụ này, các thí sinh và IOI-chan di chuyển như sau.

Dưới đây, đoạn $[L,R]$ biểu thị tập hợp các điểm có tọa độ từ $L$ đến $R$, kể cả hai đầu mút, trên trục số.

• Tại thời điểm $0$, IOI-chan đứng tại tọa độ $0$. Các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $-1$, $-2$ và $-3$.
• Tại thời điểm $1$, IOI-chan di chuyển đến tọa độ $1$. Không thí sinh nào di chuyển; các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $-1$, $-2$ và $-3$. Vì không có ai trong đoạn $[2,4]$, đáp án cho câu hỏi thứ nhất là 0.
• Tại thời điểm $2$, IOI-chan di chuyển đến tọa độ $2$. Khoảng cách giữa IOI-chan và thí sinh thứ nhất lúc này là $3$, nên thí sinh thứ nhất di chuyển đến tọa độ $1$. Các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $1$, $-2$ và $-3$. Vì chỉ có IOI-chan trong đoạn $[2,4]$, đáp án cho câu hỏi thứ hai là 1.
• Tại thời điểm $3$, IOI-chan di chuyển đến tọa độ $3$. Không thí sinh nào di chuyển; các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $1$, $-2$ và $-3$. Vì chỉ có IOI-chan trong đoạn $[2,4]$, đáp án cho câu hỏi thứ ba là 1.
• Tại thời điểm $4$, IOI-chan di chuyển đến tọa độ $4$. Khoảng cách giữa IOI-chan và thí sinh thứ nhất lúc này là $3$, nên thí sinh thứ nhất di chuyển đến tọa độ $3$. Các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $3$, $-2$ và $-3$. Vì có IOI-chan và thí sinh thứ nhất trong đoạn $[2,4]$, đáp án cho câu hỏi thứ tư là 2.
• Tại thời điểm $5$, IOI-chan di chuyển đến tọa độ $5$. Không thí sinh nào di chuyển; các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $3$, $-2$ và $-3$. Vì chỉ có thí sinh thứ nhất trong đoạn $[2,4]$, đáp án cho câu hỏi thứ năm là 1.
• Tại thời điểm $6$, IOI-chan di chuyển đến tọa độ $6$. Khoảng cách giữa IOI-chan và thí sinh thứ nhất lúc này là $3$, nên thí sinh thứ nhất di chuyển đến tọa độ $5$. Khi đó, khoảng cách giữa thí sinh thứ nhất và thí sinh thứ hai là $7$, nên thí sinh thứ hai di chuyển đến tọa độ $4$. Hơn nữa, khoảng cách giữa thí sinh thứ hai và thí sinh thứ ba lúc này là $7$, nên thí sinh thứ ba di chuyển đến tọa độ $3$. Các thí sinh thứ nhất, thứ hai và thứ ba lần lượt đứng tại các tọa độ $5$, $4$ và $3$. Vì có thí sinh thứ hai và thí sinh thứ ba trong đoạn $[2,4]$, đáp án cho câu hỏi thứ sáu là 2.

Dữ liệu vào 2

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

Dữ liệu ra 2

2
0

Ghi chú

Ví dụ này thỏa mãn các giới hạn của nhiệm vụ con 1.

Dữ liệu vào 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

Dữ liệu ra 3

1
6
0
5
2
7