시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB78473057.692%

## 문제

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

## 서브태스크

번호배점제한
11

N ≤ 200, Q ≤ 200.

26

T1 = T2 = · · · = TQ.

37

Lj = Rj (1 ≤ j ≤ Q).

46

Si ≤ 2 (1 ≤ i ≤ N).

580

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


## 채점 및 기타 정보

• 예제는 채점하지 않는다.