시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 2 100.000%

문제

There are N districts in JOI Village, numbered from 1 to N. These districts are located in a line. Now, a fire occurs in each district. At time 0, the strength of the fire in the i-th district (1 ≤ i ≤ N) is Si (Si > 0).

At time 0, the wind blows from the 1st district to the N-th district. For every pair of neighboring districts, if the fire in the upwind district is stronger than the fire in the downwind district at time t (0 ≤ t), the strength of the fire in the downwind district at time t +1 will be the strength of the fire in the upwind district at time t. Otherwise, the strength of the fire in the downwind district at time t +1 and time t are the same. Namely, if the strength of the fire in the i-th district (1 ≤ i ≤ N) at time t (0 ≤ t) is denoted by Si(t), we have Si(t) = max{Si−1(t − 1), Si(t − 1)} for every t (1 ≤ t). Here, for any t (0 ≤ t), we put S0(t) = 0. For any i (1 ≤ i ≤ N), we put Si(0) = Si.

You are a firefighter. You have Q plans to extinguish the fire. You are planning to do only one of the Q plans. In the j-th plan (1 ≤ j ≤ Q), you will use fire extinguishing agent for the k-th district for every k with Lj ≤ k ≤ Rj, and extinguish the fire in these districts. If the strength of the fire in a district is s, you need s liters of fire extinguishing agent to extinguish the fire in that district. Therefore, the amount of fire extinguishing agent needed for the j-th plan is SLj(Tj) + SLj+1(Tj) + · · · + SRj (Tj) liters. In order to examine the plan to be done, you want to know the amount of fire extinguishing agent needed for each plan.

Write a program which, given the strength of the fire at time 0 and information of fire extinguishing plans, calculates the amount of fire extinguishing agent needed for each plan.

입력

Read the following data from the standard input. Given values are all integers.

N Q
S1 . . . SN
T1 L1 R1
.
.
.
TQ LQ RQ

출력

Write Q lines to the standard output. In the j-th line (1 ≤ j ≤ Q), output the amount of fire extinguishing agent needed for the j-th plan.

제한

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ Q ≤ 200 000.
  • 1 ≤ Si ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Tj ≤ N (1 ≤ j ≤ Q).
  • 1 ≤ Lj ≤ Rj ≤ N (1 ≤ j ≤ Q).

예제 입력 1

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

예제 출력 1

21
39
33
9
27
  • At time 0, the strength of the fire in each district is 9, 3, 2, 6, 5 from the 1st district.
  • At time 1, the strength of the fire in each district is 9, 9, 3, 6, 6 from the 1st district. The amount of fire extinguishing agent needed for the 1st plan is 9 + 9 + 3 = 21 liters.
  • At time 2, the strength of the fire in each district is 9, 9, 9, 6, 6 from the 1st district. The amount of fire extinguishing agent needed for the 2nd plan is 9 + 9 + 9 + 6 + 6 = 39 liters.
  • At time 3, the strength of the fire in each district is 9, 9, 9, 9, 6 from the 1st district. The amount of fire extinguishing agent needed for the 3rd plan is 9 + 9 + 9 + 6 = 33 liters.
  • At time 4, the strength of the fire in each district is 9, 9, 9, 9, 9 from the 1st district. The amount of fire extinguishing agent needed for the 4th plan is 9 liters.
  • At time 5, the strength of the fire in each district is 9, 9, 9, 9, 9 from the 1st district. The amount of fire extinguishing agent needed for the 5th plan is 9 + 9 + 9 = 27 liters.

예제 입력 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

예제 출력 2

28
21
34
4
64
43
55
9
27
9

예제 입력 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

예제 출력 3

9
9
3
4
3
4
5
9
9
9

예제 입력 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

예제 출력 4

28
27
34
4
64
43
55
9
27
9

예제 입력 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

예제 출력 5

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