Cho dãy số ~A_1, A_2,….,A_n~ và ~M~ truy vấn. Có 2 loại truy vấn:

• Loại 1: ~1~ ~x~ ~y~ – gán giá trị của ~A_x=y~.
• Loại 2: ~2~ ~l~ ~r~ (~l \leq r~)– Yêu cầu tìm giá trị nhỏ nhất trong đoạn [~l,r~]

Input

• Dòng đầu chứa số 2 nguyên ~N,M~ (~N,M \leq 10^5~)
• Dòng thứ 2 chứa ~N~ số nguyên dương ~A_1 A_2…A_n (A_i \leq 10^9)~

~M~ dòng tiếp theo chứa ~M~ truy vấn thuộc một trong 2 loại. Tất cả các số đều dương và nhỏ hơn ~10^9~

Output

Kết quả của các truy vấn loại 2 theo thứ tự.

Sample Input

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

Sample Output

2
1
7