题目背景

翻译自 CSES-2166 题。

题目描述

给定一个包含 $n$ 个整数的数组，你需要处理 $q$ 个查询，查询的类型如下：

1. 将位置 $k$ 的值更新为 $u$。
2. 查询区间 $[a,b]$ 中的最大前缀和。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组的元素个数和查询的数量。

第二行包含 $n$ 个整数 $x_1,x_2,…,x_n$：表示数组的初始值。

接下来有 $q$ 行描述查询。每一行包含三个整数，表示以下两种类型之一：

• 1 k u：将数组中第 $k$ 个位置的值更新为 $u$。
• 2 a b：查询区间 $[a,b]$ 内的最大前缀和。

输出格式

对于每个查询类型为 2 的查询，输出该查询的结果，即区间 $[a,b]$ 中的最大前缀和。

样例

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

5
2
0

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$-10^9 \leq x_i,u \leq 10^9$；

$1 \leq k \leq n$；

$1 \leq a \leq b \leq n$。