时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个长度为 \(n\) 的整数序列：\(A[1]、A[2]、…、A[n]\)，你的任务是完成下列连个操作：

　　1 i j：需要找到子序列 \(A[i]..A[j]\)（包含 \(A[i]\) 和 \(A[j]\)）内和最大的连续子序列，即有：\(i≤x≤y≤j\)，且\(A[x]+A[x+1]+...+A[y]\) 尽量大。

　　2 i x：把 \(A[i]\) 修改成 \(x\)。

【输入格式】

　　第一行为两个整数 \(n\) 和 \(m\)，表示证书序列的长度和查询个数。
　　第二行包含 \(n\) 个整数，依次为 \(A[1],A[2],...,A[n]\) 的值。
　　再以下的 \(m\) 行每行为一个操作。

【输出格式】

　　每个查询输出一行。

【输入输出样例】

　Input

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

　Output

2
-1 

【数据限制】

　　对于 \(100\%\) 的数据满足：\(1≤n≤500 000\)，\(1≤m≤100 000\)，任何时候序列元素是绝对值不超过1000的整数。

【来源】

　　Mr.he