背景

试题来自 清华大学学生算法协会。

题目描述

省队选拔结束后，White 陷入了长时间的消沉。她在成绩中看不到任何希望。即便如此，White 仍在坚持 NOI 前的最后一段训练。除了常规训练，她开始涉足自己 OI 生涯中从未有机会学习的专题——希望在告别之前，不再留下遗憾。

甩开纷乱的思绪，White 突然聚焦在眼前的一道题上，一道朴素而枯燥的数据结构题——

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

• $1\ l\ r\ v$ — 将区间 $[l, r]$ 中的每个元素加上 $v$。
• $2\ l\ r\ v$ — 将区间 $[l, r]$ 中的每个元素赋值为 $v$。
• $3\ l\ r$ — 查询 $\sum_{i=l}^{r}(\min_{j=l}^{i} a_j) \times (\max_{j=l}^{i} a_j)$ 的值，结果对 $2^{64}$ 取模。

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

输入格式

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

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, 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}$ 取模的值。

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

35
39
40
34
177
120

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

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

提示

对于第 $1$ 个测试用例：

初始序列为 $2\ 3\ 5\ 4\ 1$。经过第 $3$ 次操作后变为 $2\ 3\ 2\ 2\ 1$，经过第 $6$ 次操作后变为 $7\ 8\ 7\ 7\ 6$。

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

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

翻译由 DeepSeek V4 Pro 完成