{"raw_statement":[{"iden":"statement","content":"小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\\dots a_n$。他希望支持两种操作：\n\n- `1 k`，给序列中的每一个元素加上一个整数 $k$；\n- `2`，查询序列中的最大子序列和。\n\n子序列指的是从原序列中去除某些元素（也可以不去除），但不破坏余下元素的相对位置形成的新的序列。例如，对于序列 $\\{2,3,4,5,6\\}$，那么 $\\{2,3,4\\},\\{2,4,6\\}$ 都是它的子序列，而 $\\{6,5,4\\}$ 不是。子序列可以为空，此时子序列和为 $0$。"},{"iden":"input","content":"第一行输入两个正整数 $n,m$，分别表示序列的长度和操作次数。\n\n第二行输入 $n$ 个整数 $a_i$，表示序列的元素。\n\n第三行开始，往下 $m$ 行，每一行分别为 `1 k` 或者 `2` 的形式，含义如题意所述。"},{"iden":"output","content":"对于每个 $2$ 操作，输出一行一个整数表示答案。"},{"iden":"note","content":"**【样例解释】**\n\n- 第一次操作求序列中的最大子序列和，则为 $12+2+8=22$；\n- 第二次操作让序列中每一个元素加上了 $3$。此时序列变为 $-2,15,-4,5,11$；\n- 第三次操作求序列中的最大子序列和，则为 $15+5+11=31$；\n- 第四次操作让序列中每一个元素加上了 $4$。此时序列变为 $2,19,0,9,15$；\n- 第五次操作求序列中的最大子序列和，则为 $2+19+9+15=45$。\n\n数据保证，$1 \\leq n,m \\leq 5\\times 10^5$，$-5\\times 10^5 \\leq a_i,k \\leq 5\\times 10^5$，操作仅为 $1$ 或 $2$ 操作。"}],"translated_statement":null,"sample_group":[["5 5\n-5 12 -7 2 8\n2\n1 3\n2\n1 4\n2","22\n31\n45"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}