Tèo đang quản lý bảng giá cổ phiếu của \(N\) công ty công nghệ. Ban đầu (ngày 0), giá cổ phiếu của công ty thứ \(i\) là \(A_i\).

Trong quá trình vận hành hệ trị giao dịch, giá cổ phiếu có sự biến động liên tục. Để phân tích xu hướng và đối chiếu lịch sử giao dịch, Tèo cần thực hiện các thao tác sau:

• 1 pos val: Cập nhật giá cổ phiếu của công ty tại vị trí \(pos\) thành \(val\). Thao tác này tạo ra một phiên bản bảng giá mới, kế thừa trực tiếp từ phiên bản hiện tại đang làm việc.
• 2 v l r: Tìm giá cổ phiếu nhỏ nhất trong các công ty từ chỉ số \(l\) đến \(r\) ở phiên bản thứ \(v\).
• 3 v: Quay lại làm việc trên phiên bản bảng giá thứ \(v\) (các cập nhật loại 1 tiếp theo sẽ kế thừa trực tiếp từ phiên bản này).

Ban đầu hệ thống ở phiên bản 0. Các phiên bản mới được đánh số tăng dần từ 1 mỗi khi có thao tác loại 1 diễn ra.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) đại diện cho giá cổ phiếu ban đầu.
• \(Q\) dòng tiếp theo chứa các yêu cầu thuộc một trong ba dạng nêu trên.

Định dạng đầu ra

• Với mỗi yêu cầu loại 2, in ra giá trị cổ phiếu nhỏ nhất tìm được trên một dòng riêng biệt.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (30% số điểm): Không có truy vấn loại 3.
• Subtask 3 (40% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

5 6
10 20 30 40 50
2 0 1 3
1 3 5
2 1 2 4
3 0
1 1 2
2 2 1 3

Output:

10
5
2

Giải thích:

• Truy vấn 1: Min từ \(1\) đến \(3\) ở bản 0 là \(\min(10, 20, 30) = 10\).
• Truy vấn 2: Cập nhật \(A_3 = 5\), tạo bản 1.
• Truy vấn 3: Min từ \(2\) đến \(4\) ở bản 1 là \(\min(20, 5, 40) = 5\).
• Truy vấn 4: Rollback về bản 0.
• Truy vấn 5: Cập nhật \(A_1 = 2\), tạo bản 2 (kế thừa từ bản 0).
• Truy vấn 6: Min từ \(1\) đến \(3\) ở bản 2 là \(\min(2, 20, 30) = 2\).