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 l r: Tính giá trị \(\min(a_l, a_{l + 1}, a_{l + 2}, ..., a_r)\).
• 2 u x: Cập nhật gán lại giá trị \(a_u \leftarrow \min(a_u, 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 \(1\) không quá \(\frac{q}{20}\).

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 l \leq r \leq n\)
• \(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ó \(l = 1\) trong mỗi truy vấn loại \(1\).
• \(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
1 5 4 3 2
1 2 4
1 3 5
2 4 2
1 3 5
1 1 5
2 3 1
1 2 4
1 2 2

3
2
2
1
1
5