[NICA #1] 序列

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\dots a_n$。他希望支持两种操作： - `1 k`，给序列中的每一个元素加上一个整数 $k$； - `2`，查询序列中的最大子序列和。 子序列指的是从原序列中去除某些元素（也可以不去除），但不破坏余下元素的相对位置形成的新的序列。例如，对于序列 $\{2,3,4,5,6\}$，那么 $\{2,3,4\},\{2,4,6\}$ 都是它的子序列，而 $\{6,5,4\}$ 不是。子序列可以为空，此时子序列和为 $0$。

第一行输入两个正整数 $n,m$，分别表示序列的长度和操作次数。 第二行输入 $n$ 个正整数 $a_i$，表示序列的元素。 第三行开始，往下 $m$ 行，每一行分别为 `1 k` 或者 `2` 的形式，含义如题意所述。

对于每个 $2$ 操作，输出一行一个整数表示答案。

5 5
-5 12 -7 2 8
2
1 3
2
1 4
2

22
31
45

**【样例解释】** - 第一次操作求序列中的最大子序列和，则为 $12+2+8=22$； - 第二次操作让序列中每一个元素加上了 $3$。此时序列变为 $-2,15,-4,5,11$； - 第三次操作求序列中的最大子序列和，则为 $15+5+11=31$； - 第四次操作让序列中每一个元素加上了 $4$。此时序列变为 $2,19,0,9,15$； - 第五次操作求序列中的最大子序列和，则为 $2+19+9+15=45$。 数据保证，$1 \leq n,m \leq 5\times 10^5$，$-5\times 10^5 \leq a_i,k \leq 5\times 10^5$，操作仅为 $1$ 或 $2$ 操作。