Truy vấn Tổng Tiền Tố

Cho mảng $n$ số nguyên. Xử lý $q$ truy vấn:

• 1 k u — Thay đổi giá trị tại vị trí $k$ thành $u$.
• 2 a b — Tìm tổng tiền tố lớn nhất trong đoạn $[a,b]$, tức là giá trị lớn nhất của $x_a+x_{a+1}+\dots +x_i$ với $a\le i\le b$ (tiền tố rỗng có tổng bằng 0 cũng được tính).

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $q$.
• Dòng thứ hai: $n$ số nguyên $x_1,x_2,\dots ,x_n$.
• $q$ dòng tiếp theo: mỗi dòng là 1 k u hoặc 2 a b.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng tiền tố lớn nhất.

Ràng buộc

• $1\le n,q\le 2\times {10}^5$
• $-{10}^9\le x_i,u\le {10}^9$
• $1\le k\le n$
• $1\le a\le b\le n$

Ví dụ