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 của các loại sau:

1. cập nhập giá trị ở vị trí \(k\) thành \(u\).
2. tổng tiền tố tối đa trong đoạn \([a,b]\) là gì?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng giá trị và truy vấn.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2,...,x_n\): các giá trị của mảng.
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có ba số nguyên: 1 k u hoặc 2 a b.

Output

• In ra kết quả của mỗi truy vấn loại 2.

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(-10^9 \leq x_i,u \leq 10^9\)
• \(1 \leq k \leq n\)
• \(1 \leq a \leq b \leq n\)

Example

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

5
2
0