X 国正受到 Y 国的攻击！为了防御，X 国设置了 $n$ 排防御工事，编号依次为 $1, 2, \dots, n$。编号为 $i$ 的防御工事的军事强度为 $a_i$。如果一个防御工事的军事强度为零，则认为该防御工事被击败。初始时，没有防御工事被击败。

战斗持续 $q$ 天，每天早上会发生以下事件之一：

• 部队调动：给定参数 $x, y$，将编号为 $x$ 的防御工事的军事强度设为 $y$。
• 增援：给定参数 $l, r, v$，将编号为 $l, l+1, \dots, r$ 的防御工事的军事强度增加 $v$（包括已经击败的防御工事）。
• 招募：所有未被击败的防御工事的军事强度增加 $1$。
• 训练：令 $b_i = \max\{r - l + 1 \mid 1 \le l \le i \le r \le n, \text{且对于所有 } l \le j \le r, a_j > 0\}$，即包含防御工事 $i$ 且未被击败的最长连续段的长度。对于所有 $1 \le i \le n$，令 $a_i := a_i + b_i$。
• 阅兵：给定参数 $l, r$，查询编号为 $l, l+1, \dots, r$ 的防御工事的总军事强度。

每天晚上会发生一次溃败事件：对于编号为 $i$ 的防御工事，如果 $i < n$ 且编号为 $i+1$ 的防御工事在当天中午之前已经被击败，那么该防御工事也将被击败（即其军事强度变为零）。

作为 X 国的总指挥官，你需要为每次“阅兵”操作提供正确的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示防御工事的数量和天数。

第二行包含 $n$ 个整数，表示 $a_1, \dots, a_n$，即每个防御工事的初始军事强度。

接下来的 $q$ 行描述了 $q$ 天中每天早上发生的事件。在第 $i$ 行中，第一个整数 $op$ 表示第 $i$ 天发生的事件类型：

• 如果 $op = 1$，发生部队调动，随后给出参数 $x, y$。
• 如果 $op = 2$，发生增援，随后给出参数 $l, r, v$。
• 如果 $op = 3$，发生招募。
• 如果 $op = 4$，发生训练。
• 如果 $op = 5$，发生阅兵，随后给出参数 $l, r$。

保证 $1 \le n, q \le 3 \times 10^5$ 且 $1 \le a_i \le 10^5$。对于部队调动事件，保证 $1 \le x \le n$ 且 $0 \le y \le 10^5$。对于增援事件，保证 $1 \le l \le r \le n$ 且 $1 \le v \le 10^5$。对于阅兵事件，保证 $1 \le l \le r \le n$。

输出格式

对于每次“阅兵”事件，输出一行一个整数，表示答案。

样例

输入 1

10 8
1 2 3 4 5 6 7 8 9 10
1 5 0
4
5 1 10
2 1 7 10
5 1 7
1 5 0
3
5 1 7

输出 1

74
97
71