Nhập vào một mảng chứa \(n\) số nguyên. Cần trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

1. Gán giá trị phần tử ở vị trí \(p\) của mảng bằng \(v\);
2. Nhập vào số \(v\), in ra chỉ số \(i\) nhỏ nhất thỏa mãn \(a[i]\geq v\). Nếu không có phần tử nào thi in ra \(-1\).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(q\): lần lượt là kích thước của mảng và số lượng truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên \(x_1,\ x_2,\ldots,\ x_n\): giá trị của các phần tử trong mảng;
• Cuối cùng là \(q\) dòng mô tả \(q\) truy vấn. Mỗi truy vấn có dạng "\(1\ p\ v\)" hoặc "\(2\ v\)".

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả trên một dòng.

Ràng buộc

• \(1\leq n,\ q\leq2\times10^5\);
• \(1\leq x_i,\ v\leq10^9\);
• \(1\leq p\leq n\);

Ví dụ

Sample input

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

Sample output

2
5 
3
-1
4