Nhập môn chia căn

Cho một mảng \(a\) gồm \(n\) số nguyên \(a_1, a_2, \ldots, 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\).

Chỉ sử dụng chia căn để giải bài này.

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, \ldots, 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 (\(1 \le x \le n\), \(|y| \le 10^9\), \(1 \le l \le r \le 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