Cho số nguyên \(n\) và dãy số nguyên không âm \(a_1,a_2,…,a_n\). Cho m truy vấn, mỗi truy vấn có dạng:

• \(1\) \(i\) \(v\): thay đổi phần tử ở vị trí \(i\) thành giá trị \(v (1≤i≤n,0≤v≤10^9).\)

• \(2\) \(l\) \(r\) : tính giá trị nhỏ nhất của các phần tử có chỉ số từ \(l\) đến \(r (1≤l≤r≤n).\)

Input

• Dòng thứ nhất chứa số nguyên \(n,m(1≤n,m≤10^5 ).\)

• Dòng thứ 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (0≤a_i≤10^9 );\)

• \(m\) dòng tiếp theo, mỗi dòng có một trong hai dạng sau:

  • \(1\) \(i\) \(v\): thay đổi phần tử ở vị trí i thành giá trị \(v (1≤i≤n,0≤v≤10^9).\)

  • \(2\) \(l\) \(r\) : tính giá trị nhỏ nhất của các phần tử có chỉ số từ \(l\) đến \(r (1≤l≤r≤n).\)

Output

• Đối với mỗi truy vấn thuộc loại thứ 2, in ra giá trị nhỏ nhất tương ứng.

Ràng buộc

• Subtask 1: 50% test có \(n,m≤10^3.\)

• Subtask 2: 50% test có \(n,m≤10^5.\)

Sample Input

5 5
6 17 9 11 4
2 3 5
2 2 2
2 5 5
2 4 5
2 5 5

Sample Output

4
17
4
4
4