JOI 村的消防活动

JOI 村共有 $N$ 个区块，每个区块都有一个编号从 $1$ 到 $N$。这些区块按照编号顺序排列在一行中。现在，每个区块都发生了火灾，时刻 $0$ 时，区块 $i$ ($1 \leq i \leq N$) 的火焰强度是 $S_i$ ($S_i > 0$)。

在时刻 $0$ 时，风开始从区块 $1$ 吹向区块 $N$。对于相邻的两个区块，在时刻 $t$ ($0 \leq t$) 时，如果风上区块的火焰强度大于风下区块的火焰强度，那么在时刻 $t+1$ 时，风下区块的火焰强度将与时刻 $t$ 时的风上区块的火焰强度相同。否则，在时刻 $t+1$ 时，风下区块的火焰强度将保持与时刻 $t$ 相同。也就是说，在时刻 $t$ ($0 \leq t$) 时，我们将区块 $i$ ($1 \leq i \leq N$) 的火焰强度记为 $S_i(t)$，那么对于 $1 \leq t$，有 $S_i(t) = \max\{S_{i-1}(t-1), S_i(t-1)\}$。其中，对于任意的 $t$ ($0 \leq t$)，定义 $S_0(t) = 0$，并且对于任意的 $i$ ($1 \leq i \leq N$)，定义 $S_i(0) = S_i$。

作为一名消防员的你计划进行 $Q$ 次灭火活动。你计划实施其中的一项计划。第 $j$ 项计划 ($1 \leq j \leq Q$) 在时刻 $T_j$，对于所有满足 $L_j \leq k \leq R_j$ 的区块 $k$，撒下灭火剂并扑灭火焰。为了扑灭火焰强度为 $s$ 的区块，需要使用 $s$ 升的灭火剂。换句话说，第 $j$ 项计划需要使用 $S_{L_j}(T_j) + S_{L_j + 1}(T_j) + \cdots + S_{R_j}(T_j)$ 升的灭火剂。

为了考虑执行哪个计划，我们想要知道每个计划所需的灭火剂的数量。

请编写一个程序，在给定时刻 $0$ 时的火焰强度信息和灭火活动计划信息下，计算出每个计划所需的灭火剂的数量。

输入

输入以以下格式从标准输入中给出。所有给定的值都是整数。

$N$ $Q$

$S_1$ $\cdots$ $S_N$

$T_1$ $L_1$ $R_1$

$\vdots$

$T_Q$ $L_Q$ $R_Q$

输出

输出应该以 $Q$ 行的形式输出到标准输出中。第 $j$ 行 ($1 \leq j \leq Q$) 应输出第 $j$ 项计划所需的消防剂的数量。

约束条件

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

子任务

1. (1 分) $N \leq 200$，$Q \leq 200$。
2. (6 分) $T_1 = T_2 = \cdots = T_Q$。
3. (7 分) $L_j = R_j$ ($1 \leq j \leq Q$)。
4. (6 分) $S_i \leq 2$ ($1 \leq i \leq N$)。
5. (80 分) 没有额外的约束条件。