高地女巫 Azusa 发现了一个长满奇异树木的花园！于是，她决定和她的朋友 Laika 一起花些时间照料这个花园。

花园可以看作是一个包含 $N$ 棵树的序列，树的编号从 $1$ 到 $N$。每棵树都有一个非负整数高度。Azusa 将按照包含 $Q$ 个条目的计划表来度过她的时间，计划表包含以下几种类型：

1. 树木砍伐阶段，由三个整数 $l, r$ 和 $k$ 确定。在此阶段，Azusa 将花费接下来的 $k$ 天砍伐树木。每天她都会找到编号在 $l$ 到 $r$ 之间最高的树，并将其高度减少 $1$。如果存在多棵高度相同的最高树，她会选择最左边的那棵。如果最高的树高度为 $0$，则当天什么也不会发生。
2. 魔法阶段，由两个整数 $i$ 和 $x$ 确定。在此阶段，Azusa 将编号为 $i$ 的树的高度修改为 $x$。
3. 树木检查阶段，由两个整数 $l$ 和 $r$ 确定。在此阶段，Azusa 将计算编号在 $l$ 到 $r$ 之间的树的高度之和。

（注意，“之间”指包含边界；例如 $1, 2, 3, 4, 5$ 都在 $1$ 和 $5$ “之间”。）

Azusa 对树木检查阶段的结果感到好奇，并希望在不遍历整个计划表的情况下知道它们。你能帮帮她吗？

交互

选手必须实现以下四个函数：

void initialise(int N, int Q, int h[]);
void cut(int l, int r, int k);
void magic(int i, int x);
long long int inspect(int l, int r);

函数 initialise 会接收 $N$（树的数量）、$Q$（计划表中的条目数）以及一个数组 $h$，其中 $h[i]$ 是第 $i$ 棵树的高度，对于 $1 \le i \le N$。该函数会被评测系统的代码调用恰好一次，且在调用其他三个函数之前。cut、magic 和 inspect 函数分别代表树木砍伐、魔法和树木检查阶段，并由各自的参数确定。选手实现的 inspect 函数必须返回编号在 $l$ 到 $r$ 之间的树的高度之和。

选手不应实现 main 函数。这将由评测系统的 grader.cpp 文件实现；附件中会提供一个样例 grader.cpp。我们的 main 函数将读取 $N, Q$、包含 $N$ 个初始高度的序列以及 $Q$ 个计划表条目。三种类型的计划表条目（cut(l, r, k)、magic(i, x) 和 inspect(l, r)）分别编码为 1 l r k、2 i x 和 3 l r。这是下文样例中使用的输入格式。

注意，选手可以使用全局变量、额外的函数、方法和类。

数据范围

• $1 \le N, Q \le 300\,000$
• 保证 cut、magic 和 inspect 函数总共会被调用恰好 $Q$ 次。
• $1 \le i \le N$
• $0 \le x, k, h[i] \le 1\,000\,000\,000$
• $1 \le l \le r \le N$

样例

输入 1

6 10
1 2 3 1 2 3
1 1 6 3
3 1 6
1 1 3 3
3 1 6
1 1 3 1000
3 1 6
2 1 1000
3 1 6
1 1 3 999
3 1 5

输出 1

9
6
5
1005
4

说明

在第一阶段，经过 3 天的树木砍伐后，树的高度分别为 $1, 2, 2, 1, 2, 3$；$1, 2, 2, 1, 2, 2$；以及 $1, 1, 2, 1, 2, 2$。这些值的和为 $9$，这是第二阶段检查的答案。

在第三阶段，经过 3 天的树木砍伐后，树的高度分别为 $1, 1, 1, 1, 2, 2$；$0, 1, 1, 1, 2, 2$；以及 $0, 0, 1, 1, 2, 2$。这些值的和为 $6$，这是第四阶段检查的答案。

在第五阶段，经过 1000 天的树木砍伐后，树的高度为 $0, 0, 0, 1, 2, 2$。这是因为高度为 $0$ 的树无法被砍伐。这些值的和为 $5$，这是第六阶段检查的答案。

在第七阶段，第一棵树生长到高度 $1000$，得到树的高度为 $1000, 0, 0, 1, 2, 2$。这些值的和为 $1005$，这是第八阶段检查的答案。

在第九阶段，999 天的树木砍伐中，每一天都将第一棵树的高度减少 $1$。这使得该阶段结束时树的高度为 $1, 0, 0, 1, 2, 2$。前五棵树的值之和为 $4$，这是第十阶段（最终阶段）检查的答案。