Problem Description

In JOI Village, there are $ N $ sections numbered from $ 1 $ to $ N $. These sections are arranged in a single row in numerical order. Currently, each section is on fire, and the fire intensity in section $ i $ ($1 \leq i \leq N$) at time $ 0 $ is $ S_i $ ($ S_i > 0 $).

At time $ 0 $, the wind starts blowing from section $ 1 $ towards section $ N $. For two adjacent sections, if the fire in the upwind section is stronger than the fire in the downwind section at time $ t $ ($0 \leq t$), then the fire intensity in the downwind section at time $ t + 1 $ will become the same as the fire intensity in the upwind section at time $ t $. Otherwise, the fire intensity in the downwind section at time $ t + 1 $ remains the same as at time $ t $. That is, if we denote the fire intensity in section $ i $ at time $ t $ ($0 \leq t$) as $ S_i(t) $, then for $1 \leq t$, $S_i(t) = \max{S_{i - 1}(t - 1), S_i(t - 1)}$. Note that for any $ t $ ($0 \leq t$), $ S_0(t) = 0 $, and for any $ i $ ($1 \leq i \leq N$), $ S_i(0) = S_i $.

As a firefighter, you have planned $ Q $ fire suppression activities. You plan to implement only one of these plans. The $ j $-th plan ($1 \leq j \leq Q$) involves spraying fire retardant at all sections $ k $ where $L_j \leq k \leq R_j$ at time $ T_j $, extinguishing those sections. Extinguishing a section with fire intensity $ s $ requires $ s $ liters of fire retardant. That is, the $ j $-th plan requires $S_{L_j}(T_j) + S_{L_j + 1}(T_j) + \cdots + S_{R_j}(T_j)$ liters of fire retardant.

To evaluate which plan to execute, you want to know the amount of fire retardant required for each plan.

Given the information on fire intensities at time $ 0 $ and the details of the fire suppression plans, create a program to calculate the amount of fire retardant needed for each plan.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ N $ $ Q $ $ S_1 $ $\cdots$ $ S_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 \leq j \leq Q$) should contain the amount of fire retardant needed for the $ j $-th plan.

Sample Input and Output

Sample Input #1

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

Sample Output #1

21
39
33
9
27

Sample Input #2

10 10
3 1 4 1 5 9 2 6 5 3
1 1 6
2 8 10
4 2 7
8 3 3
6 1 10
3 2 8
5 1 9
7 4 5
9 7 9
10 10 10

Sample Output #2

28
21
34
4
64
43
55
9
27
9

Sample Input #3

10 10
3 1 4 1 5 9 2 6 5 3
1 6 6
2 8 8
4 2 2
8 3 3
6 1 1
3 4 4
5 5 5
7 10 10
9 8 8
10 7 7

Sample Output #3

9
9
3
4
3
4
5
9
9
9

Sample Input #4

10 10
3 1 4 1 5 9 2 6 5 3
7 1 6
7 8 10
7 2 7
7 3 3
7 1 10
7 2 8
7 1 9
7 4 5
7 7 9
7 10 10

Sample Output #4

28
27
34
4
64
43
55
9
27
9

Sample Input #5

20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20

Sample Output #5

25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq Q \leq 200,000$.
• $1 \leq S_i \leq 1,000,000,000$ ($1 \leq i \leq N$).
• $1 \leq T_j \leq N$ ($1 \leq j \leq Q$).
• $1 \leq L_j \leq R_j \leq N$ ($1 \leq j \leq Q$).

Subtasks

1. ($ 1 point $) $N \leq 200$, $Q \leq 200$.
2. ($ 6 points $) $T_1 = T_2 = \cdots = T_Q$.
3. ($ 7 points $) $ L_j = R_j $ ($1 \leq j \leq Q$).
4. ($ 6 points $) $S_i \leq 2$ ($1 \leq i \leq N$).
5. ($ 80 points $) No additional constraints.

Sample Explanation 1

• The fire intensities in each section at time $ 0 $ are, in order from section $ 1 $, $ 9, 3, 2, 6, 5 $.
• The fire intensities in each section at time $ 1 $ are, in order from section $ 1 $, $ 9, 9, 3, 6, 6 $. Therefore, the amount of fire retardant needed for the 1st plan is $ 9 + 9 + 3 = 21 $ liters.
• The fire intensities in each section at time $ 2 $ are, in order from section $ 1 $, $ 9, 9, 9, 6, 6 $. Therefore, the amount of fire retardant needed for the 2nd plan is $ 9 + 9 + 9 + 6 + 6 = 39 $ liters.
• The fire intensities in each section at time $ 3 $ are, in order from section $ 1 $, $ 9, 9, 9, 9, 6 $. Therefore, the amount of fire retardant needed for the 3rd plan is $ 9 + 9 + 9 + 6 = 33 $ liters.
• The fire intensities in each section at time $ 4 $ are, in order from section $ 1 $, $ 9, 9, 9, 9, 9 $. Therefore, the amount of fire retardant needed for the 4th plan is $ 9 $ liters.
• The fire intensities in each section at time $ 5 $ are, in order from section $ 1 $, $ 9, 9, 9, 9, 9 $. Therefore, the amount of fire retardant needed for the 5th plan is $ 9 + 9 + 9 = 27 $ liters.

Sample Input #1 satisfies the constraints of Subtasks 1 and 5.

Sample Explanation 2

Sample Input #2 satisfies the constraints of Subtasks 1 and 5.

Sample Explanation 3

Sample Input #3 satisfies the constraints of Subtasks 1, 3, and 5.

Sample Explanation 4

Sample Input #4 satisfies the constraints of Subtasks 1, 2, and 5.

Sample Explanation 5

Sample Input #5 satisfies the constraints of Subtasks 1, 4, and 5.

见题面 Input 部分

见题面 Output 部分