Migrated from Lutece 1598 加帕里公园的friends

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

我还有很多话想和她说，还有很多地方想和她去，把$Kaban$酱还给我！——$Sabaru$

薮猫酱为了从天蓝怪手里拯救小包，必须发现天蓝怪们的弱点所在。
具体来说，$n$只天蓝怪组成了一个序列$A$，每一只有一个战斗力数值$A_i$，
之后会发生$m$个事件，事件共有两种类型，有可能是
$1$、薮猫酱给你一个区间$[a,b]$，要你输出 $\max \{A_p+A_{p+1}+{\ldots}+A_q\}\ (a\leq p \leq q \leq b)$
$2$、第$pos$只天蓝怪的战斗力变成了$X$

Input

第一行是两个整数$n$、$m$，
第二行包含$n$个整数$A_1,A_2,{\ldots},A_n$，
接下来$m$行，每行三个整数，可能是
$1\;a\;b$，代表薮猫酱的一次询问；
$2\;pos\;X$，代表某只天蓝怪战斗力的变化。

Output

对于每次询问，单独输出一行，代表答案。

Samples

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3

2
-1

Note

$1{\leq}n{\leq}500000$，
$1{\leq}m{\leq}100000$，
$-1000{\leq}A_i{\leq}1000$，
$1{\leq}a{\leq}b{\leq}n$，
$1{\leq}pos{\leq}n$，
$-1000{\leq}X{\leq}1000$

Resources

17暑假前集训-数据结构专题 By AutSky_JadeK，思路非原创 - Vijos 1083