409011 - 区间最大子段和

给定序列,支持单点修改,每次询问区间 [L, R] 内连续子段的最大和。

输入

第一行两个整数 n 和m(1 ≤ n ≤ 5 × 105,1 ≤ m ≤ 105),代表序列长度、操作次数。 接下来 n 行,依次给出序列初始值。 之后 m 行,每行三个整数 k, x, y: 1.k = 1:查询区间 [x, y] 的最大子段和; 2.k = 2:单点修改,将第 x 位赋值为 s (1 ≤∣s∣≤ 1000)。

输出

每次查询,输出对应区间最大子段和。

样例

输入

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

输出

2
-1
Time Limit 1 second
Memory Limit 256 MB
Stats
上一题 下一题