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$