Doraemon là một chú mèo máy đến từ thế kỷ ~22~ với chiếc túi thần kỳ chứa hàng ngàn món bảo bối độc đáo. Để chuẩn bị cho đợt bảo dưỡng định kỳ tại Xưởng Chế Tạo Mèo Máy, Doraemon quyết định lấy các bảo bối ra để kiểm kê và đánh giá lại mức năng lượng của chúng. Một ngày nọ, khi đang loay hoay sắp xếp trong căn phòng nhỏ, Nobita nhìn thấy Doraemon xếp các món bảo bối thành một hàng dài tăm tắp. Mỗi món bảo bối đều tỏa ra một luồng ánh sáng lấp lánh, tượng trưng cho chỉ số sức mạnh công nghệ của tương lai. Bị cuốn hút, Nobita hỏi Doraemon về ý nghĩa của việc này và được biết rằng đây là "Hàng Bảo Bối Năng Lượng" – một quy trình quản lý nghiêm ngặt để đảm bảo không có món đồ nào bị trục trặc khi sử dụng.

Bị sự kỳ diệu của công nghệ thế kỷ ~22~ hấp dẫn, Nobita xin phép được phụ giúp Doraemon quản lý danh sách bảo bối này thông qua một chiếc máy tính bảng mini. Không phải là sự ghi chép lộn xộn, hệ thống quản lý của Doraemon hoạt động dựa trên một cấu trúc:

• Cấu trúc hàng bảo bối:

  • Doraemon xếp ~N~ món bảo bối thành một hàng ngang, được đánh số thứ tự từ ~1~ đến ~N~ theo chiều từ trái sang phải. Ban đầu, món bảo bối ở vị trí thứ ~i~ có chỉ số năng lượng là một số nguyên dương ~a_i~.

• Quy tắc vận hành hệ thống: Trong quá trình kiểm tra, Doraemon và Nobita sẽ thực hiện ~Q~ thao tác thuộc một trong hai dạng sau:

  • Dạng 1 (Nâng cấp năng lượng): Khi phát hiện bảo bối ở vị trí thứ ~i~ bị hao hụt pin hoặc vừa được nâng cấp linh kiện mới, Doraemon sẽ thay đổi giá trị của phần tử thứ ~i~ thành ~p~.
  • Dạng 2 (Truy xuất bảo bối tối ưu): Để chọn ra món đồ phù hợp giải cứu Nobita khỏi những rắc rối thường ngày, Doraemon cần xét các bảo bối nằm liên tiếp từ vị trí ~L~ đến vị trí ~R~, sau đó tìm số lớn thứ ~K~ trong đoạn ~[L, R]~ đó (khi sắp xếp chỉ số năng lượng của các bảo bối trong đoạn theo thứ tự không tăng).

Vì số lượng bảo bối và các đợt kiểm tra là rất lớn, Nobita đang hoa cả mắt với những con số. Bạn hãy lập trình giúp Doraemon và Nobita xử lý thật nhanh các truy vấn này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~, lần lượt là số lượng bảo bối và số lượng truy vấn ~(N, Q \leq 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ thể hiện chỉ số năng lượng ban đầu của các bảo bối ~(a_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn bắt đầu bằng một số nguyên ~type~:
  • Với ~type = 0~, theo sau là hai số nguyên dương ~i~ và ~p~ – thể hiện truy vấn dạng 1: thay đổi giá trị của phần tử thứ ~i~ thành ~p~ ~(1 \leq i \leq N; p \leq 10^9)~.
  • Với ~type = 1~, theo sau là ba số nguyên dương ~L, R~ và ~K~ – thể hiện truy vấn dạng 2: tìm số lớn thứ ~K~ trong đoạn ~[L, R]~ ~(1 \leq L \leq R \leq N; 1 \leq K \leq R - L + 1)~.

Output

• Với mỗi truy vấn thuộc dạng 2 (~type = 1~), in ra trên một dòng một số nguyên duy nhất là đáp án tìm được.

Example Input

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

Example Output

4
3

Giải thích

• Ban đầu, dãy chỉ số năng lượng của ~5~ bảo bối là: ~[1, 3, 2, 4, 5]~.
• Truy vấn 1 (0 1 5): Thay đổi chỉ số của bảo bối thứ ~1~ thành ~5~. Dãy năng lượng trở thành: ~[5, 3, 2, 4, 5]~.
• Truy vấn 2 (1 1 5 3): Xét đoạn từ ~1~ đến ~5~ là ~[5, 3, 2, 4, 5]~. Khi sắp xếp từ lớn đến bé ta được: ~5, 5, 4, 3, 2~. Giá trị lớn thứ ~K = 3~ trong đoạn này là ~4~.
• Truy vấn 3 (1 2 4 2): Xét đoạn từ ~2~ đến ~4~ là ~[3, 2, 4]~. Khi sắp xếp từ lớn đến bé ta được: ~4, 3, 2~. Giá trị lớn thứ ~K = 2~ trong đoạn này là ~3~.

Ràng buộc

• Subtask ~1~ (~15\%~ số điểm): ~N, Q \leq 10^3~.
• Subtask ~2~ (~15\%~ số điểm): ~N, Q \leq 5 \times 10^4~ và ~K = 1~.
• Subtask ~3~ (~15\%~ số điểm): ~K = R - L + 1~.
• Subtask ~4~ (~15\%~ số điểm): ~N, Q \leq 2\times10^4~ và ~a_i, p \leq 50~.
• Subtask ~5~ (~15\%~ số điểm): ~N, Q \leq 5 \times 10^4~ và ~K \leq 10~.
• Subtask ~6~ (~5\%~ số điểm): ~L = 1; R = N~ và ~a_i, p \leq 10^6~.
• Subtask ~7~ (~5\%~ số điểm): ~L = 1; R = N~.
• Subtask ~8~ (~5\%~ số điểm): ~N, Q \leq 3 \times 10^4~ và ~type_i = 1~.
• Subtask ~9~ (~5\%~ số điểm): ~N, Q \leq 3 \times 10^4~.
• Subtask ~10~ (~5\%~ số điểm): Không có ràng buộc gì thêm.