我们将一个整数数组 $b$ 的长度为 $m$ 的权重定义为其元素之和的绝对值，即 $|b_1 + b_2 + \dots + b_m|$。

我们将数组 $c$ 划分为若干个子数组的“美观度”定义为这些子数组权重中的最小值。形式上，将数组 $c$ 划分为 $k$ 个子数组 $[c_1, \dots, c_{p_1}], [c_{p_1+1}, \dots, c_{p_2}], \dots, [c_{p_{k-1}+1}, \dots, c_{p_k}]$（其中 $1 \le p_1 < p_2 < \dots < p_{k-1} < p_k = n$）的美观度为 $\min(|c_1 + \dots + c_{p_1}|, |c_{p_1+1} + \dots + c_{p_2}|, \dots, |c_{p_{k-1}+1} + \dots + c_{p_k}|)$。例如，将数组 $[3, -6, 4, 5, -8]$ 划分为 $[3, -6], [4], [5, -8]$，其美观度为 $\min(|3+(-6)|, |4|, |5+(-8)|) = \min(3, 4, 3) = 3$。

我们将数组 $c$ 的“美观度”定义为在其所有可能的子数组划分方式中，美观度的最大值。

给定一个长度为 $n$ 的整数数组 $a$。你需要执行 $q$ 次查询。查询分为两种类型： 1. 查找由元素 $[a_l, a_{l+1}, \dots, a_r]$ 组成的数组的美观度，其中 $(l, r)$ 为查询参数； 2. 将元素 $a_x$ 替换为 $v$，其中 $(x, v)$ 为查询参数。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n, q \le 10^6$)，分别表示数组 $a$ 的长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示数组 $a$ 的元素。

接下来的 $q$ 行，每行包含三个整数。第一个整数 $type_i$ ($1 \le type_i \le 2$) 表示查询类型。第一类查询格式为“$1\ l\ r$” ($1 \le l \le r \le n$)，第二类查询格式为“$2\ x\ v$” ($1 \le x \le n, -10^9 \le v \le 10^9$)。

输出格式

对于每个第一类查询，在单独的一行中输出一个整数，即相应数组的美观度。

子任务

1. (4 分): $type_i = 1$ 对于所有 $1 \le i \le q$；$a_i > 0$ 对于所有 $1 \le i \le n$；
2. (14 分): $type_i = 1$ 对于所有 $1 \le i \le q$；$n, q \le 1000$；
3. (10 分): $type_i = 1$ 对于所有 $1 \le i \le q$；$n, q \le 2 \cdot 10^5$，且对于每个查询，存在不超过 2 个子数组的最优划分；
4. (10 分): $type_i = 1$ 对于所有 $1 \le i \le q$；$q \le n \le 2 \cdot 10^5, l_i = 1, r_i = i$ 对于所有 $1 \le i \le q$；
5. (11 分): $type_i = 1$ 对于所有 $1 \le i \le q$；$n, q \le 2 \cdot 10^5, -5 \le \sum_{j=1}^i a_j \le 5$ 对于所有 $1 \le i \le n$；
6. (18 分): $type_i = 1$ 对于所有 $1 \le i \le q$；$n, q \le 2 \cdot 10^5$；
7. (9 分): $type_i = 1$ 对于所有 $1 \le i \le q$；
8. (16 分): $n, q \le 2 \cdot 10^5$；
9. (8 分): 无附加限制。

样例

输入 1

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

输出 1

5
3
3
1

输入 2

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

输出 2

2
2
12
7

说明

在第一个样例中，对于第三个查询，数组 $[-3, 4, 2, -5]$ 的最大美观度划分方式为 $[-3], [4, 2], [-5]$。

在第二个样例中，对于第一个查询，数组 $[1, -2, 3, -4]$ 的最大美观度划分方式为 $[1, -2, 3], [-4]$。