Cho mảng ~a~ gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~ và ~q~ truy vấn thuộc một trong hai loại:

1. Cho hai số nguyên ~k, x~, gán ~a_k \leftarrow x~.

2. Cho hai số nguyên ~l, r~, tìm giá trị của phần tử nhỏ nhất trong đoạn con ~a_l, a_{l+1}, \dots, a_r~.

Yêu cầu: Với mỗi truy vấn loại ~2~, in ra giá trị phần tử nhỏ nhất cần tìm.

Input

Dòng đầu chứa hai số nguyên ~n, q~ là kích thước mảng ~a~ và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (với ~0 \leq a_i \leq 10^9~) mô tả mảng ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả các truy vấn:

• Đối với truy vấn loại 1, ba số nguyên này lần lượt là ~1 \space k \space x~ (với ~1 \leq k \leq n~ và ~0 \leq x \leq 10^9~).

• Đối với truy vấn loại 2, ba số nguyên này lần lượt là ~2 \space l \space r~ (với ~1 \leq l \leq r \leq n~).

Output

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq n, q \leq 5000~.

• Subtask ~2~ (chiếm ~40\%~ số điểm): ~1 \leq n, q \leq 4 \cdot 10^5~.

• Subtask ~3~ (chiếm ~40\%~ số điểm): ~1 \leq n, q \leq 10^6~.

Sample Input 1

7 6
1 4 2 5 9 7 4
2 2 4
1 3 10
2 2 7
2 4 5
1 7 6
2 6 7

Sample Output 1

2
4
5
6

Sample Input 2

6 6
8 3 5 9 9 3
2 2 5
2 3 6
1 3 8
2 1 6
1 5 5
2 6 6

Sample Output 2

3
3
3
3