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≤n,q≤2⋅10^5\)
• \(−10^9≤x_i,u≤10^9\)
• \(1≤k≤n\)
• \(1≤a≤b≤n\)

Example

Sample input

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

Sample output

5
2
0