在参加 IOI 2023 之前，你需要解决以下练习题。

你有一个长度为 $n$ 的序列 $a$。你需要执行 $q$ 次查询：

1. 给定 $v$，将所有 $a_i$ 修改为 $\min(a_i, v)$。
2. 将所有 $a_i$ 修改为 $a_i + i$。
3. 给定 $l, r$，输出 $\sum_{i=l}^{r} a_i$。

你可能无法参加 IOI 2023，但这道题依然值得一做。因此，Little Cyan Fish 请你来解决它！

输入格式

第一行包含两个整数 $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^{12}$)。 接下来的 $q$ 行描述了所有查询，格式如下：

• $1 \ v$ ($0 \le v \le 10^{12}$)：将所有 $a_i$ 修改为 $\min(a_i, v)$。
• $2$：将所有 $a_i$ 修改为 $a_i + i$。
• $3 \ l \ r$ ($1 \le l \le r \le n$)：输出 $\sum_{i=l}^{r} a_i$。

输出格式

对于每个类型为 3 的查询，输出一行，包含一个整数，表示答案。

样例

输入 1

13 11
6 14 14 6 3 6 4 13 10 3 12 5 11
1 2
2
2
2
1 11
3 4 6
2
1 6
2
1 9
3 2 13

输出 1

33
107