Bob đang theo dõi biến động chỉ số giá cổ phiếu của một doanh nghiệp công nghệ lớn trong vòng \(N\) ngày, được đánh số từ \(1\) đến \(N\). Giá cổ phiếu ở ngày thứ \(i\) ban đầu là \(A_i\). Trong quá trình quan sát, Bob cần xử lý \(Q\) truy vấn thuộc hai loại:

• 1 pos val: Giá trị cổ phiếu ở ngày thứ \(pos\) có sự điều chỉnh tăng/giảm thành giá trị mới là \(val\).
• 2 R: Bob muốn biết giá trị cổ phiếu cao nhất đạt được trong khoảng thời gian từ ngày \(1\) đến ngày \(R\).

Hãy lập trình giúp Bob thực hiện việc thống kê giá cổ phiếu.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) là giá cổ phiếu ban đầu của các ngày (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo chứa các truy vấn (\(1 \le pos \le N\), \(1 \le R \le N\), \(1 \le val \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra giá trị cổ phiếu cao nhất tìm được.

Ví dụ

Input:

5 4
10 20 5 30 15
2 3
1 3 25
2 3
2 5

Output:

20
25
30