省队选拔结束后，White 陷入了漫长的失落之中。她无法在自己的成绩中看到任何希望。即便如此，White 依然坚持着 NOI 前的最后训练。除了常规训练外，她也开始探索那些在她的 OI 生涯中从未有机会学习的课题——希望在告别之前，不再留下遗憾。

甩开脑海中杂乱的思绪，White 突然将注意力集中在眼前的一道题目上，这是一道朴实而枯燥的数据结构题——

White 有一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$。她将对该序列执行 $q$ 次操作。每次操作为以下三种类型之一：

• 1 l r v — 将区间 $[l, r]$ 内的每个元素加上 $v$。
• 2 l r v — 将区间 $[l, r]$ 内的每个元素赋值为 $v$。
• 3 l r — 查询 $\sum_{i=l}^{r} \left(\min_{j=l}^{i} a_j\right) \times \left(\max_{j=l}^{i} a_j\right) \pmod{2^{64}}$ 的值。

你的任务是模拟所有操作并输出所有查询的结果。

输入格式

输入的第一行包含两个整数 $n, q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示元素的数量和操作的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示初始元素。

接下来的 $q$ 行，每行描述一个操作，格式为以下三种之一：

• 1 l r v ($1 \le l \le r \le n$, $-10^9 \le v \le 10^9$)，表示区间加操作。
• 2 l r v ($1 \le l \le r \le n$, $1 \le v \le 10^9$)，表示区间赋值操作。
• 3 l r ($1 \le l \le r \le n$)，表示查询操作。

保证在整个过程中，对于每个 $1 \le i \le n$，始终满足 $0 \le a_i \le 10^9$。

输出格式

对于每个查询操作，单行输出一个整数，即查询结果模 $2^{64}$ 的值。

样例

输入样例 1

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

输出样例 1

35
39
40
34
177
120

输入样例 2

10 20
1 2 3 4 5 6 7 8 9 10
1 1 10 1
3 1 5
3 2 9
3 8 10
1 2 5 10
3 1 5
3 2 9
3 8 10
1 5 9 -5
3 1 5
3 2 9
3 8 10
1 2 5 -10
3 1 5
3 2 9
3 8 10
1 5 9 5
3 1 5
3 2 9
3 8 10

输出样例 2

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

说明

在第一个样例中：

原始序列为 2 3 5 4 1。在第三次操作（2 4 5 2）后，序列变为 2 3 2 2 1；在第六次操作（1 1 2 5）后，序列变为 7 8 7 7 6。

对于第一次查询，答案为 $\sum_{i=1}^{5}\left(\min_{j=1}^{i} a_j\right) \times \left(\max_{j=1}^{i} a_j\right) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$。

对于第二次查询，答案为 $\sum_{i=2}^{4}\left(\min_{j=2}^{i} a_j\right) \times \left(\max_{j=2}^{i} a_j\right) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$。