该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

输入一个长度为n的整数序列，以及m条指令，每条指令可能是以下两种之一：
“2 x y”，把 A[x] 改成 y。
“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 max(x≤l≤r≤y)⁡ { ∑(i=l~r) A[i] }。
对于每个询问，输出一个整数表示答案。
第一行两个整数n,m
第二行n个整数A1~An
接下来m行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改
对于每个询问输出一个整数表示答案,每个答案之间要换行
100%满足n≤500000,m≤100000,|Ai|<=1000,其他所有数据（包括答案）在int范围内

输入样例

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

输出样例

2
-1

样例解释

初始序列为1 2 -3 4 5
第一次询问[2,3]之间的最大子段和为2
然后将序列修改为1 -1 -3 4 5
第二次询问[2,3]之间的最大子段和为-1
注意：
1)第二次询问时交换了区间的左右端点
2)最大子段和必须为连续的一段，并且长度至少为1

时空限制

每个测试点1s
空间262144KB

数据范围

100%满足n≤500000,m≤100000,|Ai|<=1000,其他所有数据（包括答案）在int范围内