Bạn được cho một mảng gồm n số nguyên. Nhiệm vụ của bạn là xử lý q truy vấn với hai loại sau:

Cập nhật giá trị tại vị trí k thành u.

Tìm tổng tiền tố lớn nhất trong đoạn [a, b].

Dữ liệu vào:

Dòng đầu tiên: hai số nguyên n và q

n → số phần tử trong mảng

q → số lượng truy vấn.

Dòng thứ hai: n số nguyên x₁, x₂, ..., xₙ → các giá trị ban đầu của mảng.

Sau đó có q dòng, mỗi dòng mô tả một truy vấn:

1 k u → gán xₖ = u.

2 a b → tìm tổng tiền tố lớn nhất trong đoạn [a, b].

Dữ liệu ra:

Với mỗi truy vấn loại 2, in ra một số nguyên: → giá trị của tổng tiền tố lớn nhất trong đoạn [a, b].

Ràng buộc

1 ≤ n, q ≤ 2 * 10^5

-10^9 ≤ xᵢ, u ≤ 10^9

1 ≤ k ≤ n

1 ≤ a ≤ b ≤ n

Ví dụ :

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