Segment tree 1

Cho một mảng \(a\) gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Bạn cần xử lý \(q\) truy vấn trên mảng ban đầu, mỗi truy vấn có thể là một trong hai loại:

• \(1 \; x \; y\) — Gán \(a_x := y\)
• \(2 \; l \; r\) — In ra giá trị lớn nhất trong đoạn từ \(a_l\) đến \(a_r\)

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\))
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn theo định dạng mô tả ở trên.

Output

Với mỗi truy vấn loại 2, in ra một dòng là giá trị lớn nhất trong đoạn được yêu cầu.

Scoring

• Subtask 1 (20%): \(n, q \le 1000\)
• Subtask 2 (80%): Không có ràng buộc thêm

Sample Input 1

5 4
1 3 -2 4 5
2 2 5
1 3 7
2 2 5
2 1 3

Sample Output 1

5
7
7