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\) và và số lượng phàn tử bằng giá trị nhỏ nhất 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\) và và số lượng phàn tử bằng giá trị nhỏ nhất 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 hai số nguyên, giá trị nhỏ nhất trên đoạn \([l,r]\) và số lượng phần tử bằng giá trị nhỏ nhất \((1≤l≤r≤n).\)

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
11 13 13 13 10
2 2 5
2 5 5
1 5 13
2 2 3
2 1 3

Sample Output

10 1
10 1
13 2
11 1