Cho một dãy \(a\) có \(n\) số nguyên, các phần tử được đáng số từ \(1\) đến \(n\). Hãy giải quyết \(q\) truy vấn có dạng:

• 1 u: Tính giá trị \(\min(a_1, a_2, a_3, ..., a_u)\).
• 2 u x: Cập nhật gán lại giá trị \(a_u \leftarrow x\).

Bài này có một giới hạn đặc biệt như sau:

• Số lượng truy vấn loại \(2\) không quá \(\frac{q}{20}\) cho các test khác test ví dụ.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\ (1 \leq n, q \leq 10^6)\) là số lượng phần tử trong dãy và số lượng truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3, ..., a_n\ (1 \leq a_i \leq 10^9)\) là dãy \(a\) ban đầu.

\(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo dạng đã mô tả ở trên. Dữ liệu đảm bảo rằng:

• \(1 \leq u \leq n\)
• \(1 \leq x \leq 10^9\)

Output

Với mỗi truy vấn loại \(1\), in ra kết quả trên một dòng.

Scoring

• \(30\%\) số điểm có \(x \leq a_u\) trong mỗi truy vấn loại \(2\).
• \(30\%\) số điểm có \(n, q \leq 2 \times 10^5\).
• \(40\%\) số điểm còn lại không có giới hạn gì thêm.

Example

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

4
2
5
6
2