小 D 是一位数据结构大师，他特别喜欢研究形式简单的数据结构，今天他想到了这样一道题目：

你有一个长度为 $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$。

顶级数据结构大师小 D 轻松的解决了这个问题，现在他打算来考考即将参加 IOI2022 的你，相信你也可以轻松解决这个问题。

输入格式

第一行两个正整数 $n,q$ 表示序列的长度与修改/询问的个数。

下面一行 $n$ 个整数 $a_i$，表示初始序列 $a$。

下面 $q$ 行，每行第一个正整数 $o{p}_i$ 表示第 $i$ 次修改/询问的类型。

若 $o{p}_i=1$，则下面紧跟一个整数 $v_i$，表示进行一次修改 1。

若 $o{p}_i=2$，则表示进行一次修改 2。

若 $o{p}_i=3$，则下面紧跟两个正整数 $l_i,r_i$，表示进行一次询问 3。

输出格式

若干行，每行一个整数表示答案。

样例

input

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

output

33
9
107

数据范围与提示

$1\le n,q\le 2\times {10}^5,0\le a_i,v_i\le {10}^{12}$

性质 A 为：$a_i,v_i$ 在 $[0,{10}^{12}]$ 随机生成，$o{p}_i$ 在 $[1,3]$ 随机生成，$[l_i,r_i]$ 在所有可行区间随机生成。

时间限制：$\mathtt{\text{3s}}$

空间限制：$\mathtt{\text{512MB}}$