题目描述

Marko 在院子里用木柱搭建了一个柱状图：$n$ 根宽度为 $1$ 的柱子紧挨着排列，第 $i$ 个位置的柱子高度为 $h_i$。Marko 喜欢修改自己的作品，因此有时会升高、降低或替换其中的一些柱子。

有时，Marko 只观察柱状图的一部分，即位置从 $l$ 到 $r$ 的柱子，并想象有大量雨水落在这些柱子上。此时，观察范围之外的柱子视为不存在，因此水可以从第 $l$ 根柱子的左边界和第 $r$ 根柱子的右边界流走。雨会一直下，直到柱状图蓄满水：被两侧较高柱子挡住的水会留下，其余的水全部流走。一个装满水的 $1\times 1$ 方格所容纳的水量为 $1$ 单位。

如果一根柱子的顶部上方有水，就称这根柱子完全被水淹没。如果柱子的顶部是干燥的，也就是说顶部上方没有水，就称它没有完全被水淹没。水仍然可以从侧面接触这样的柱子，水面最高可以与柱顶齐平。

Marko 将依次进行 $q$ 个事件，每个事件属于以下五种类型之一：

• 1 i x：将第 $i$ 根柱子的高度改为 $x$。
• 2 l r x：将第 $l$ 根到第 $r$ 根柱子的高度全部改为 $x$。
• 3 l r x：将第 $l$ 根到第 $r$ 根柱子的高度全部增加 $x$（$x$ 也可以为负数）。
• 4 l r：Marko 观察第 $l$ 根到第 $r$ 根柱子，询问其中有多少根柱子没有完全被水淹没。
• 5 l r：Marko 观察第 $l$ 根到第 $r$ 根柱子，询问这些柱子总共能蓄积多少单位的水。

请帮助 Marko 回答所有询问。观察不会改变柱状图，每次询问结束后，水都会消失。

输入格式

第一行包含两个正整数 $n$ 和 $q$（$1\le n,q\le 200\,000$），分别表示柱子的数量和事件的数量。

第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$（$0\le h_i\le 10^9$），表示各根柱子的初始高度。

接下来 $q$ 行，每行以上述格式之一描述一个事件。满足 $1\le i\le n$，$1\le l\le r\le n$。对于类型 $1$ 和类型 $2$ 的事件，$0\le x\le 10^9$；对于类型 $3$ 的事件，$-10^9\le x\le 10^9$。

保证在任何时刻，所有柱子的高度都是 $0$ 到 $10^9$ 之间的整数。

输出格式

对于每个类型 $4$ 或类型 $5$ 的事件，按照它们在输入中出现的顺序，各用一行输出该询问的答案。

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

4
4
1
3
2
5

6 5
5 1 3 2 4 1
5 1 6
4 1 6
5 2 5
5 4 6
4 3 3

6
3
1
0
1

5 8
2 0 1 0 3
5 1 5
4 1 5
3 2 4 2
5 1 5
2 1 3 1
5 1 5
1 4 5
4 1 5

5
2
1
0
5

提示

样例 1 解释

柱状图的高度为 $[3,0,2,4,1,4,0,2]$。第一次询问中，Marko 观察整个柱状图。第 $2$、$3$、$5$、$7$ 根柱子上方分别蓄有 $3$、$1$、$3$、$2$ 单位的水，而第 $1$、$4$、$6$、$8$ 根柱子的顶部是干燥的。这四根柱子没有完全被水淹没，所以答案为 $4$。

第二次询问中，Marko 观察的柱子高度为 $[0,2,4,1]$。高度先上升再下降，因此所有水都会从左边界或右边界流走。没有柱子完全被水淹没，答案为 $4$。

样例 2 解释

柱状图的高度为 $[5,1,3,2,4,1]$。当 Marko 观察整个柱状图时，第 $1$ 根和第 $5$ 根柱子之间的水面高度为 $4$，而第 $5$ 根柱子右侧的水会全部流走。因此，各根柱子上方分别蓄有 $0,3,1,2,0,0$ 单位的水，总计 $6$ 单位。第 $2$、$3$、$4$ 根柱子完全被水淹没，其余三根没有，所以第二次询问的答案为 $3$。

评分与子任务