Under construction

Still being built. Things may change

Fire

Time limit2sMemory limit512 MB

Summary
Given fire strengths that spread downwind over T steps, answer Q queries for the total fire strength in a range [L, R] at time T.
Level

Hard8 of 10

Topics
Sliding window, Divide and conquer, Prefix sum
Solved
No attempts yet

Statement

JOI Village has N districts numbered 1 to N, arranged in a line. A fire breaks out in every district. At time 0, the fire strength in district i is S_i (S_i > 0).

At time 0, the wind blows from district 1 toward district N. For each pair of neighboring districts, if the fire in the upwind district is stronger than the fire in the downwind district at time t (t ≥ 0), the downwind fire at time t+1 takes the strength of the upwind fire at time t. Otherwise, the downwind strength stays the same. Let S_i(t) be the strength of the fire in district i at time t. Then

Si(t)=max⁡{Si−1(t−1),Si(t−1)}(t≥1)S_i(t) = \max\{S_{i-1}(t-1), S_i(t-1)\} \quad (t \geq 1)

where S_0(t) = 0 for all t ≥ 0 and S_i(0) = S_i.

You are a firefighter with Q plans, and you carry out exactly one of them. In plan j, you spray extinguishing agent on every district k with L_j ≤ k ≤ R_j. Putting out a fire of strength s takes s liters of agent. So plan j needs S_{L_j}(T_j) + S_{L_j+1}(T_j) + ... + S_{R_j}(T_j) liters. For each plan, compute the amount of agent required.

Input

The first line contains N and Q. The second line contains S_1, S_2, ..., S_N. Each of the next Q lines contains T_j, L_j, and R_j.

N Q
S_1 S_2 ... S_N
T_1 L_1 R_1
...
T_Q L_Q R_Q

Output

Print Q lines. On line j, print the amount of extinguishing agent needed for plan j.

Constraints

  • 1 ≤ N ≤ 200 000
  • 1 ≤ Q ≤ 200 000
  • 1 ≤ S_i ≤ 1 000 000 000 (1 ≤ i ≤ N)
  • 1 ≤ T_j ≤ N (1 ≤ j ≤ Q)
  • 1 ≤ L_j ≤ R_j ≤ N (1 ≤ j ≤ Q)

Examples5

  1. Example 1

    Input
    5 5
9 3 2 6 5
1 1 3
2 1 5
3 2 5
4 3 3
5 3 5
    Expected output
    21
39
33
9
27

  2. Example 2

    Input
    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
    Expected output
    28
21
34
4
64
43
55
9
27
9

  3. Example 3

    Input
    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
    Expected output
    9
9
3
4
3
4
5
9
9
9

  4. Example 4

    Input
    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
    Expected output
    28
27
34
4
64
43
55
9
27
9

  5. Example 5

    Input
    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
    Expected output
    25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40