题目描述

小 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$ 操作。