Description

在最后的最后，珂朵莉给了你一个长为 $n$ 的序列，有 $m$ 个操作：

1. 全局加（即序列的所有数加）。
2. 查询区间最大子段和。

Input Format

第一行两个整数 $n,m$。

第二行 $n$ 个数表示这个序列。

之后 $m$ 行，每行一个操作。

• $1\ x$ : 所有数都加上 $x$。
• $2\ l\ r$ : 查询区间 $[l,r]$ 内的最大子段和（可以不选数，此时最大子段和是 $0$）。

Output Format

对于每个询问，输出一个数表示答案。

5 7
-10 -3 -2 -4 -5
2 2 4
1 5
2 2 4
1 3
2 1 5
1 2
2 3 5

0
6
18
19

Hint

Idea：nzhtl1477，Solution：ccz181078，Code：nzhtl1477&w33z8kqrqk8zzzx33，Data：nzhtl1477

$1\leq n \leq 3\times 10^5$，$1 \leq m \leq 6\times 10^5$，序列中的数绝对值 $\leq 2\times 10^9$，$1$ 操作中的 $x$ 的绝对值 $\leq 5\times 10^7$。