Problem Description

It's the 22nd century, and thanks to Pitaro, the new principal of Ootemae High School, the Ootemae Procon has become a globally瞩目 event.

At the opening ceremony of Ootemae Procon 21XX, N students will march in a single file. The path they march on is represented as a number line. All students march facing the positive direction on the number line. At time 0, the i-th student from the front (1 ≤ i ≤ N) is standing at coordinate −i. At coordinate 0, Principal Pitaro, the flag bearer, is standing.

Principal Pitaro moves one unit per unit time in the positive direction on the path.

Each student has a defined value called "lethargy". The lethargy of the i-th student from the front is D_i. Each student takes the following action simultaneously per unit time:

• The i-th student from the front at time 0 moves one unit in the positive direction on the path if the distance to the participant (student or Principal Pitaro) in front of them at time 0 is exactly D_i. Otherwise, they do not move.

You are Kitaru, the head teacher, who came to watch the opening ceremony. Unfortunately, you slept through the entire ceremony and now must take photos. To cover up your mistake, you decide to take a photo of the venue and draw the participants on it.

To avoid exposing your cover-up and to estimate the effort needed for drawing, you want to know the following Q values:

• The number of participants standing at coordinates between L_j and R_j inclusive at time T_j (1 ≤ j ≤ Q)

Given the lethargy of each student and the information for Q queries, create a program that calculates the number of participants satisfying the conditions for each query.

Input Format

Input is given from the standard input in the following format:

$ N $ $ Q $ $ D_1 $ $\vdots$ $ D_N $ $ T_1 $ $ L_1 $ $ R_1 $ $\vdots$ $ T_Q $ $ L_Q $ $ R_Q $

Output Format

Output Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) should contain the integer representing the answer to the j-th query.

Sample Input and Output

Sample 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

Sample Output #1

0
1
1
2
1
1

Sample Input #2

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

Sample Output #2

2
0

Sample 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

Sample Output #3

0
2
0
4
1
4

Notes/Hints

Constraints

• All inputs are integers.
• $1\ \leq\ N\ \leq\ 500\,000$.
• $1\ \leq\ Q\ \leq\ 500\,000$.
• $1\ \leq\ D_i\ \leq\ 1\,000\,000\,000$ $(1\ \leq\ i\ \leq\ N)$.
• $1\ \leq\ T_j\ \leq\ 1\,000\,000\,000$ $(1\ \leq\ j\ \leq\ Q)$.
• $1\ \leq\ L_j\ \leq\ R_j\ \leq\ 1\,000\,000\,000$ $(1\ \leq\ j\ \leq\ Q)$.

Subtasks

1. ($ 15 $ points) $N,\ Q,\ D_i,\ T_j,\ L_j,\ R_j\ \leq\ 1\,000$ $(1\ \leq\ i\ \leq\ N,\ 1\ \leq\ j\ \leq\ Q)$.
2. ($ 16 $ points) $T_i\ =\ T_j$ $(1\ \leq\ i,j\ \leq\ Q)$.
3. ($ 69 $ points) No additional constraints.

见题面 Input 部分

见题面 Output 部分