题目描述

译自 JOI 2020 Final T5「火事 / Fire」

在 JOI 世界里有 $N$ 个地区排成一条线。为了方便，我们将这些地区编号为 $1$ 到 $N$。突然，各个地区都起火了。在时刻 $0$，第 $i$ 个区的火势大小为 $S_i$。

此时（时刻 $0$），一阵风从 $1$ 号地区一直吹到了 $N$ 号地区。对于每两个相邻的地区，如果 $t$ 时刻上风地区的火势比下风地区的强，$t+1$ 时刻下风地区的火势大小将变为 $t$ 时刻上风地区的火势，否则 $t+1$ 和 $t$ 时刻时下风地区的火势大小不变。
形式化地说，如果 $t$ 时刻 $i$ 地区的火势为 $S_i(t)$，则 $Si(t)=\max{S{i-1}(t-1),S_i(t-1)}$，其中 $S_0(t)=0,~S_i(0)=S_i$。

你是一位消防员。现在，你想到了 $Q$ 种灭火方案，并打算执行其中一种。你的第 $j$ 种方案是在 $T_j$ 时刻对 $[L_j,~Rj]$ 中的所有地区使用灭火剂完全扑灭火灾。
对于一个火势大小为 $s$ 的城市，你将需要 $s$ 升的灭火剂来扑灭火灾。因此，执行方案 $j$ 总共要花费 $S{L_j}(Tj)+S{L_j+1}(Tj)+\cdots +S{R_j}(T_j)$ 升灭火剂。
译者注：英文版题面中没有定义 $T_j$，此处定义从日文版中提取。

为了更好地选取灭火方案，你的任务是编写一个程序，给出 $0$ 时刻的火势大小，计算各个方案所需的灭火剂量。

输入格式

第一行两个数 $N,~Q$，含义如题面所示。
接下来一行 $N$ 个数 $S_1\dots S_N$，表示初始时的火势大小。
接下来 $Q$ 行每行三个数 $T_j,~L_j,~R_j$，表示方案 $j$ 的相关信息。

输出格式

输出 $Q$ 行，第 $i$ 行表示方案 $j$ 所需的灭火剂量。

样例 1

input

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

output

21
39
33
9
27

• 时刻 $0$ 时地区 $1$ 到 地区 $N$ 的火势大小分别为 $9,~3,~2,~6,~5$。
• 时刻 $1$ 时地区 $1$ 到 地区 $N$ 的火势大小分别为 $9,~9,~3,~6,~6$。方案 $1$ 需要的灭火剂量为 $9+9+3=21$ 升。
• 时刻 $2$ 时地区 $1$ 到 地区 $N$ 的火势大小分别为 $9,~9,~9,~6,~6$。方案 $2$ 需要的灭火剂量为 $9+9+9+6+6=39$ 升。
• 时刻 $3$ 时地区 $1$ 到 地区 $N$ 的火势大小分别为 $9,~9,~9,~9,~6$。方案 $3$ 需要的灭火剂量为 $9+9+9+6=33$ 升。
• 时刻 $4$ 时地区 $1$ 到 地区 $N$ 的火势大小分别为 $9,~9,~9,~9,~9$。方案 $4$ 需要的灭火剂量为 $9$ 升。
• 时刻 $5$ 时地区 $1$ 到 地区 $N$ 的火势大小分别为 $9,~9,~9,~9,~9$。方案 $5$ 需要的灭火剂量为 $9+9+9=27$ 升。

该样例满足子任务 $1$ 和子任务 $5$ 的限制。

样例 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

output

28
21
34
4
64
43
55
9
27
9

该样例满足子任务 $1$ 和子任务 $5$ 的限制。

样例 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

output

9
9
3
4
3
4
5
9
9
9

该样例满足子任务 $1,~3,~5$ 的限制。

样例 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

output

28
27
34
4
64
43
55
9
27
9

该样例满足子任务 $1,~2,~5$ 的限制。

样例 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

output

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

该样例满足子任务 $1,~4,~5$ 的限制。

数据范围与提示

对于所有测试数据 $1\le N,Q\le 2\times 10^5,~1\le S_i\le 10^9,~1\le L_j,~R_j,~T_j\le N$。