Bạn được cho một mảng $x_1, x_2, \dots, x_n$. Bạn cần thực hiện hai loại truy vấn trên mảng này.

• Cho $i$ và $y$, gán $x_i = y$.
• Cho $l$, tìm giá trị $d$ nhỏ nhất trong tất cả các bộ $(a, b, c, d)$ thỏa mãn $l \le a < b < c < d$ và $x_a < x_b < x_c < x_d$, hoặc trả lời rằng không tồn tại bộ như vậy.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, q$ ($1 \le n, q \le 500\,000$): số lượng phần tử trong mảng và số lượng truy vấn.

Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$).

Mỗi dòng trong $q$ dòng tiếp theo chứa mô tả của một truy vấn.

Nếu số nguyên đầu tiên trong dòng bằng 1, thì hai số nguyên tiếp theo là $i$ và $y$ ($1 \le i \le n, 1 \le y \le 10^9$), mô tả một truy vấn loại thứ nhất.

Ngược lại, nếu số nguyên đầu tiên trong dòng bằng 2, thì số nguyên tiếp theo là $l$ ($1 \le l \le n$), mô tả một truy vấn loại thứ hai.

Dữ liệu ra

Với mỗi truy vấn loại thứ hai, hãy trả về giá trị $d$ nhỏ nhất trong tất cả các bộ $(a, b, c, d)$ sao cho $l \le a < b < c < d$ và $x_a < x_b < x_c < x_d$, hoặc in ra "-1" nếu không tồn tại bộ như vậy.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4
5
6
-1
-1
11