有 $N$ 个观测塔，按顺序编号为 $0$ 到 $N-1$。对于 $0 \le i \le N-1$，第 $i$ 个观测塔的高度为 $H[i]$。每个观测塔还有一个观测分数 $S[i]$，初始时所有观测分数均为 $0$。

对于 $0 \le i < j \le N-1$，若对所有满足 $i \le k \le j-1$ 的 $k$ 都有 $H[k] < H[j]$，则称从塔 $i$ 可以观测到塔 $j$。注意，编号 $j \le i$ 的塔无法从塔 $i$ 观测到。

当从某个塔进行一次观测时，该塔可以观测到的所有塔的观测分数都会增加 $1$。

现在会依次发生 $Q$ 个事件。每个事件属于以下三种类型之一：

• 观测：对于满足 $0 \le I \le N-2$ 的 $I$，从第 $I$ 个塔进行一次观测。
• 测量：对于满足 $0 \le L \le R \le N-1$ 的 $L, R$，计算从塔 $L$ 到塔 $R$ 的观测分数之和，即计算 $S[L] + \cdots + S[R]$。
• 地壳移动：对于满足 $0 \le L \le R \le N-1$ 以及 $-10^9 \le V \le 10^9$ 的 $L, R, V$，将区间 $[L, R]$ 内所有塔的高度增加 $V$，即对每个 $H[L], \dots, H[R]$ 加上 $V$。

观测事件可表示为数组 $[I]$，测量事件表示为数组 $[L, R]$，地壳移动事件表示为数组 $[L, R, V]$。由于不同类型事件对应数组长度不同，可以通过数组大小判断事件类型。

事件按 $0$ 到 $Q-1$ 的顺序依次发生，第 $i$ 个事件为 $E[i]$。

设测量事件总数为 $K$，按照发生顺序将其编号为第 $0$ 个到第 $K-1$ 个测量事件。你需要输出所有测量事件的结果，即依次输出第 $0$ 个到第 $K-1$ 个测量事件的答案。

实现细节

你需要实现以下函数：

vector<long long> tower_events(vector<int> H, vector<vector<int>> E)

• $H$：大小为 $N$ 的整数数组。
• $E$：大小为 $Q$ 的数组，每个元素是一个表示事件的整数数组。

该函数应返回一个大小为 $K$ 的整数数组 $X$，其中 $X[i]$ 为第 $i$ 个测量事件的结果（$0 \le i \le K-1$）。

该函数仅会被调用一次。

输入格式

样例评测器的输入格式如下：

• 第 1 行：$N$ $Q$
• 第 2 行：$H[0]\ H[1]\ \dots\ H[N-1]$
• 对于所有 $0 \le i \le Q-1$：
  • 第 $3+i$ 行：$|E[i]| \ E[i][0]\ \dots\ E[i][|E[i]|-1]$

输出格式

样例评测器的输出格式如下：

• 对于所有 $0 \le i \le K-1$：
  • 第 $1+i$ 行：$X[i]$

限制

• $5 \le N \le 1,000,000$
• $1 \le Q \le 250,000$
• $1 \le H[i] \le 10^9$（$0 \le i \le N-1$）
• 对于每个观测事件：$0 \le I \le N-2$
• 对于每个测量事件：$0 \le L \le R \le N-1$
• 对于每个地壳移动事件：$0 \le L \le R \le N-1$
• 对于每个地壳移动事件：$-10^9 \le V \le 10^9$
• 每次地壳移动事件之后，所有塔的高度均至少为 $1$，即 $1 \le H[i]$（$0 \le i \le N-1$）
• 至少存在一次测量事件

子任务

样例数据

样例 1

考虑如下函数调用：

tower_events([1, 2, 3, 4, 5], [[0], [1, 3], [1, 2, 1], [1], [0, 4]])

第一次事件之后：

$H = [1, 2, 3, 4, 5]$, $S = [0, 1, 1, 1, 1]$

第二次事件为第 $0$ 个测量事件，其结果为：

$S[1] + S[2] + S[3] = 3$

第三次事件之后：

$H = [1, 3, 4, 4, 5]$, $S = [0, 1, 1, 1, 1]$

第四次事件之后：

$H = [1, 3, 4, 4, 5]$, $S = [0, 1, 2, 1, 2]$

最后一次事件为第 $1$ 个测量事件，其结果为：

$S[0] + \cdots + S[4] = 6$

因此函数应返回：

$[3, 6]$

样例 2

考虑如下函数调用：

tower_events([7, 7, 9, 5, 8, 10, 2, 9, 2, 2], [[1], [6, 8, 6], [1], [1, 9], [3], [8], [2, 4], [5], [1, 1, 7], [1], [0, 9]])

函数应返回：

$[5, 3, 10]$