Cho dãy \(n\) số nguyên \(a_1,a_2,\ldots,a_n\). Hãy thực hiện \(Q\) truy vấn, mỗi truy vấn có một trong hai dạng sau:

• \(1\) \(k\) \(V\): Đặt \(a_k=V\)
• \(2\) \(u\) \(v\): In ra \(\min⁡(a_u,a_{u+1},\ldots,a_v)\)

Input

• Dòng đầu chứa hai số nguyên dương \(n,Q\) \((1 \leq n,Q \leq 2 \times 10^5)\)
• Dòng thứ hai chứa n số nguyên \(a_1,a_2,\ldots,a_n\) \((1 \leq a_i \leq 10^9)\)
• Tiếp theo là \(Q\) dòng, mỗi dòng mô tả một truy vấn theo dạng mô tả như trên. Chú ý \(1 \leq V \leq 10^9;1 \leq u \leq v \leq n\)

Output

• Với mỗi truy vấn loại \(2\) in một số nguyên trên một dòng là kết quả tìm được

Example

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

2
1
3