Sau khi xác định được chính xác các khu vực cần phải khai thác, các Nấm lại đặt ra câu hỏi lớn rằng khu vực tài nguyên phong phú như vậy có lẽ nào sẽ bị nhiều động vật hung dữ để mắt đến hay không. Vì để cẩn trọng chúng bắt đầu hoạch định lại các khu vực cần khai thác, Chính xác là khu vực có giá trị phong phú thứ hai của các đề xuất trước đó. Nhưng trong quá trình lên kế hoạch chúng phát hiện rằng đã có nhưng nơi tính toán sai lệch mức độ phong phú cần được thay đổi lại giá trị. Chúng không tài nào có thể xử lý cả hai cùng một lúc, bạn hãy giúp các Nấm hoạch định lại kế hoạch nhé.

Cụ thể, có ~2~ loại truy vấn:

• ~0~ ~p~ ~x~: Thay đổi mức độ phong phú của khu vực ~p~ thành ~x~.
• ~1~ ~l~ ~r~: Trả lời kết quả của đề xuất khai thác từ khu vực ~l~ đến ~r~, nếu không tồn tại hãy in ra ~-1~.

Input

Dòng đầy tiên là cặp giá trị ~n~ và ~q~.

Dòng thứ hai, Gồm ~n~ giá trị ~a_i~.

~q~ dòng tiếp theo, là các truy vấn ~0~ ~p~ ~x~ hoặc ~1~ ~l~ ~r~.

Output

Gồm các dòng của truy vấn loại ~1~, Ứng với mỗi đề xuất của các Nấm hãy đưa ra kết quả cần thiết.

Constraints

~1 \le n, q \le 10^5~

~1 \le a_i \le 10^5~

~1 \le l_i \le r_i \le n~

~1 \le p, x \le n~

Input Sample 1

5 4
1 3 2 5 4
1 2 3
0 3 3
1 2 3
1 1 5

Output Sample 1

2
-1
4

Subtask

• SubTask ~1~: ~90~% số test ứng với ~q \le 10^3~
• SubTask ~2~: ~10~% số test còn lại, không ràng buộc gì thêm