Tổng đoạn con

Bạn có một dãy số nguyên gồm $n$ phần tử. Trải qua thời gian, dãy số này liên tục thay đổi và bạn cần xử lý một loạt các truy vấn được đưa ra.

Có tổng cộng $q$ truy vấn, mỗi truy vấn là một trong hai loại sau:

Loại 1: 1 $k$ $u$ --- Cập nhật giá trị phần tử ở vị trí $k$ thành $u$.
Loại 2: 2 $a$ $b$ --- Trong tất cả các đoạn con bắt đầu tại $a$ và kết thúc tại $i$ với $a \le i \le b$, hãy tìm đoạn con có tổng lớn nhất.

Cụ thể hơn, với truy vấn loại 2, bạn cần xét các đoạn $[a, a], [a, a+1], \dots, [a, b]$ và chọn ra đoạn có tổng lớn nhất.

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 \le n, q \le 2 \cdot 10^5$) --- độ dài ban đầu của dãy và số lượng truy vấn.
Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, \dots, x_n$ ($-10^9 \le x_i \le 10^9$) --- các phần tử ban đầu của dãy.
$q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng:
1 $k$ $u$ --- cập nhật $x_k \leftarrow u$, với $1 \le k \le n$, $-10^9 \le u \le 10^9$.
2 $a$ $b$ --- truy vấn tổng lớn nhất của một đoạn con bắt đầu tại $a$ và kết thúc tại một vị trí bất kỳ trong đoạn $[a, b]$, với $1 \le a \le b \le n$.

Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả tương ứng --- tổng lớn nhất của đoạn con được yêu cầu.

Test 1

Input

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

Output

5
2
0

Note

Ban đầu, dãy là: $[1, 2, -1, 3, 1, -5, 1, 4]$
Truy vấn 2 2 6: các đoạn cần xét là $[2,2], [2,3], [2,4], [2,5], [2,6]$ có tổng lần lượt là: $2,1,4,5,0$ $\Rightarrow$ đáp án là $5$.
Truy vấn 1 4 -2: cập nhật phần tử thứ 4 thành $-2$.
Dãy trở thành: $[1, 2, -1, -2, 1, -5, 1, 4]$
Truy vấn 2 2 6: đoạn có tổng lớn nhất là $[2,3,4]$ với tổng $2 -1 -2 = -1$, nhưng $[2,5]$ có tổng $2 -1 -2 +1 = 0$, nên đáp án là $2$ từ $[2,2]$.
Truy vấn 2 3 4: đoạn có tổng lớn nhất là $0$.

Điều hướng chính