JOI 村有 $N$ 个区，编号从 $1$ 到 $N$。这些区排成一行。现在，每个区都发生了火灾。在时间 $0$，第 $i$ 个区 ($1 \le i \le N$) 的火势强度为 $S_i$ ($S_i > 0$)。

在时间 $0$，风从第 $1$ 个区吹向第 $N$ 个区。对于每一对相邻的区，如果在时间 $t$ ($0 \le t$)，上风向区的火势强于下风向区，则在时间 $t+1$，下风向区的火势强度将变为时间 $t$ 时上风向区的火势强度。否则，下风向区在时间 $t+1$ 和时间 $t$ 的火势强度相同。即，如果用 $S_i(t)$ 表示第 $i$ 个区 ($1 \le i \le N$) 在时间 $t$ ($0 \le t$) 的火势强度，则对于每个 $t$ ($1 \le t$)，有 $S_i(t) = \max\{S_{i-1}(t-1), S_i(t-1)\}$。这里，对于任何 $t$ ($0 \le t$)，我们令 $S_0(t) = 0$。对于任何 $i$ ($1 \le i \le N$)，我们令 $S_i(0) = S_i$。

你是一名消防员。你有 $Q$ 个灭火计划。你计划只执行这 $Q$ 个计划中的一个。在第 $j$ 个计划 ($1 \le j \le Q$) 中，你将对所有满足 $L_j \le k \le R_j$ 的第 $k$ 个区使用灭火剂，并扑灭这些区的火。如果一个区的火势强度为 $s$，则你需要 $s$ 升灭火剂来扑灭该区的火。因此，第 $j$ 个计划所需的灭火剂总量为 $S_{L_j}(T_j) + S_{L_j+1}(T_j) + \dots + S_{R_j}(T_j)$ 升。

为了审查该计划，你需要知道每个计划所需的灭火剂总量。

编写一个程序，给定时间 $0$ 的火势强度和灭火计划的信息，计算每个计划所需的灭火剂总量。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N \ Q$ $S_1 \dots S_N$ $T_1 \ L_1 \ R_1$ $\vdots$ $T_Q \ L_Q \ R_Q$

输出格式

向标准输出写入 $Q$ 行。在第 $j$ 行 ($1 \le j \le Q$) 中，输出第 $j$ 个计划所需的灭火剂总量。

数据范围

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

子任务

1. (1 分) $N \le 200, Q \le 200$
2. (6 分) $T_1 = T_2 = \dots = T_Q$
3. (7 分) $L_j = R_j$ ($1 \le j \le Q$)
4. (6 分) $S_i \le 2$ ($1 \le i \le N$)
5. (80 分) 无附加限制

样例

输入格式 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

说明

• 在时间 $0$，各区的火势强度从第 $1$ 个区起依次为 $9, 3, 2, 6, 5$。
• 在时间 $1$，各区的火势强度从第 $1$ 个区起依次为 $9, 9, 3, 6, 6$。第 $1$ 个计划所需的灭火剂总量为 $9 + 9 + 3 = 21$ 升。
• 在时间 $2$，各区的火势强度从第 $1$ 个区起依次为 $9, 9, 9, 6, 6$。第 $2$ 个计划所需的灭火剂总量为 $9 + 9 + 9 + 6 + 6 = 39$ 升。
• 在时间 $3$，各区的火势强度从第 $1$ 个区起依次为 $9, 9, 9, 9, 6$。第 $3$ 个计划所需的灭火剂总量为 $9 + 9 + 9 + 6 = 33$ 升。
• 在时间 $4$，各区的火势强度从第 $1$ 个区起依次为 $9, 9, 9, 9, 9$。第 $4$ 个计划所需的灭火剂总量为 $9$ 升。
• 在时间 $5$，各区的火势强度从第 $1$ 个区起依次为 $9, 9, 9, 9, 9$。第 $5$ 个计划所需的灭火剂总量为 $9 + 9 + 9 = 27$ 升。

输入格式 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