We define the weight of an array of integers $b$ of length $m$ as the absolute value of the sum of its elements, i.e., $|b_1 + b_2 + \dots + b_m|$.

We define the beauty of a partition of an array $c$ into several subarrays as the minimum weight among the weights of the subarrays. Formally, the beauty of a partition of an array $c$ into $k$ subarrays $[c_1, \dots, c_{p_1}], [c_{p_1+1}, \dots, c_{p_2}], \dots, [c_{p_{k-1}+1}, \dots, c_{p_k}]$, where $1 \le p_1 < p_2 < \dots < p_{k-1} < p_k = n$, is the value $\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}|)$. For example, the partition of the array $[3, -6, 4, 5, -8]$ into subarrays $[3, -6], [4], [5, -8]$ has a beauty of $\min(|3+(-6)|, |4|, |5+(-8)|) = \min(3, 4, 3) = 3$.

We define the beauty of an array $c$ as the maximum beauty among all its possible partitions into subarrays.

You are given an array of integers $a$ of length $n$. You need to perform $q$ queries. The queries are of two types:

1. Find the beauty of the array consisting of the elements $[a_l, a_{l+1}, \dots, a_r]$, where $(l, r)$ are the query parameters.
2. Replace the element $a_x$ with $v$, where $(x, v)$ are the query parameters.

Input

The first line contains two integers $n, q$ ($1 \le n, q \le 10^6$) — the length of the array $a$ and the number of queries, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of the array $a$.

The next $q$ lines each contain three integers. The first number $type_i$ ($1 \le type_i \le 2$) denotes the type of the query. Queries of the first type are given in the format "1 l r" ($1 \le l \le r \le n$), and queries of the second type are given in the format "2 x v" ($1 \le x \le n, -10^9 \le v \le 10^9$).

Output

For each query of the first type, output one integer on a separate line — the beauty of the corresponding array.

Subtasks

1. (4 points): $type_i = 1$ for $1 \le i \le q$; $a_i > 0$ for $1 \le i \le n$;
2. (14 points): $type_i = 1$ for $1 \le i \le q$; $n, q \le 1000$;
3. (10 points): $type_i = 1$ for $1 \le i \le q$; $n, q \le 2 \cdot 10^5$, for each query there exists an optimal partition into no more than 2 subarrays;
4. (10 points): $type_i = 1$ for $1 \le i \le q$; $q \le n \le 2 \cdot 10^5$, $l_i = 1, r_i = i$ for $1 \le i \le q$;
5. (11 points): $type_i = 1$ for $1 \le i \le q$; $n, q \le 2 \cdot 10^5$, $-5 \le \sum_{j=1}^i a_j \le 5$ for $1 \le i \le n$;
6. (18 points): $type_i = 1$ for $1 \le i \le q$; $n, q \le 2 \cdot 10^5$;
7. (9 points): $type_i = 1$ for $1 \le i \le q$;
8. (16 points): $n, q \le 2 \cdot 10^5$;
9. (8 points): no additional constraints.

Examples

Input 1

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

Output 1

5
3
3
1

Input 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

Output 2

2
2
12
7

Note

In the first example, for the third query, the maximum beauty of the partition of the array $[-3, 4, 2, -5]$ is achieved by partitioning it into subarrays $[-3], [4, 2], [-5]$.

In the second example, for the first query, the maximum beauty of the partition of the array $[1, -2, 3, -4]$ is achieved by partitioning it into subarrays $[1, -2, 3], [-4]$.