Cho mảng \(A\) gồm \(n\) số nguyên. Cho \(q\) truy vấn thuộc một trong hai dạng:

• \(1\) \(i\) \(x\): Gán \(A_i\) thành \(x\)
• \(2\) \(l\) \(r\): Tìm giá trị lớn nhất trong đoạn \(A_l, A_{l+1}... A_r\)

Dữ liệu vào

• Dòng đầu tiên là số \(n, q\) \((1 \le n \le 10^5, 1 \le q \le 10^5)\)
• Dòng thứ hai là \(n\) số nguyên \(A_i\) \((|A_i| \le 10^9)\)
• \(q\) dòng sau, mỗi dòng là một truy vấn thuộc một trong hai loại trên.

Dữ liệu ra

• Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input 1

5 6
1 4 2 3 5
2 1 3
1 3 3
2 1 5
2 3 5
1 2 3
2 2 4

Output 1

4
5
5
3