You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

在人气动漫 Black Rock shooter 中,当加贺里对麻陶 说出了“滚回去“以后,与此同时,在另一个心灵世界里, BRS 也遭到了敌人的攻击。此时,一共有 $n$ 个攻击排成一行 朝着她飞了过来,每个攻击有一个伤害值。并且每个攻击伤 害可能随时变化。BRS 的攻击可以打掉一段连续的攻击。现 在,给出 $m$ 段攻击,求出 BRS 最多可以打掉此段里多少的 伤害(就是说从给定一段里选择连续一段打掉)。伤害从 $1$ 到 $n$ 编号。

Input Format

第一行 $2$ 个整数: $n , m$

第二行 $n$ 个数:第 $i$ 个数代表第 $i$ 个攻击

第 $3$ 到 $2+m$ 行:每行三个数 $k,x,y$。

若 $k=1,x,y$ 代表查询的区间。

若 $k=2$ ,代表第 $x$ 个攻击伤害改为了 $y$ 所有的伤害值绝对值$<=1000$

Output Format

对于每次 $k=1$ ,输出一个整数代表最大值

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

2
-1​

Hint

对于 $100\%$ 的数据：$n\le 5\times 10^5, m \le 10^5$