Ngân là quản lý của một thư viện kỹ thuật số chứa hàng ngàn cuốn sách. Mỗi cuốn sách trong thư viện có một số lượng trang nhất định, và vì một số lý do như việc cập nhật nội dung hoặc bổ sung chương mới, số lượng trang của sách có thể thay đổi theo thời gian.

Ngoài ra, Ngân cũng phải đáp ứng các yêu cầu từ độc giả, những người muốn tìm các cuốn sách phù hợp với tiêu chí về số lượng trang mà họ mong muốn. Họ sẽ đưa ra yêu cầu tìm những cuốn sách có số lượng trang lớn hơn hoặc bằng một con số nhất định trong một khoảng sách cụ thể (ví dụ: từ cuốn sách thứ \(L\) đến cuốn sách thứ \(R\)).

Bài toán: Ngân cần xây dựng một hệ thống xử lý hai loại yêu cầu sau:

• Yêu cầu thay đổi số lượng trang: \(1\) \(i\) \(v\): Thay đổi số lượng trang của cuốn sách tại vị trí \(i\) thành \(v\) trang.
• Yêu cầu tìm kiếm sách phù hợp: \(2\) \(L\) \(R\) \(k\): Tìm cuốn sách có số lượng trang nhỏ nhất nhưng lớn hơn hoặc bằng \(k\) trong khoảng sách từ vị trí \(L\) đến \(R\).

Dữ liệu vào

• Dòng đầu tiên ghi \(2\) số \(N\) và \(M\) là số lượng sách ban đầu trong thư viện và số truy vấn \((1 \le N, M \le 10^5)\).
• Dòng tiếp theo gồm \(N\) số, mỗi số tương ứng với số lượng trang của một cuốn sách.
• \(M\) dòng tiếp theo, mỗi dòng ghi một truy vấn nằm trong \(1\) trong \(2\) loại trên.
• Các số trong input đều lớn hơn hoặc bằng \(1\) và nhỏ hơn hoặc bằng \(10^9\)

Dữ liệu ra

• Với mỗi truy vấn loại \(2\) ghi trên \(1\) dòng đáp số.

Input 1

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

Output 1

3
-1
2

Input 2

8 5
2 5 8 8 8 8 2 4
1 3 4 
1 3 7 
2 2 6 5
2 1 5 9
2 1 7 5

Output 2

5
-1
5