배열 $x_1, x_2, \dots, x_n$이 주어진다. 이 배열에 대해 두 가지 유형의 쿼리를 수행해야 한다.

• $i$와 $y$가 주어지면, $x_i = y$로 설정한다.
• $l$이 주어지면, $l \le a < b < c < d$이고 $x_a < x_b < x_c < x_d$를 만족하는 모든 튜플 $(a, b, c, d)$ 중에서 가장 작은 $d$를 찾거나, 그러한 튜플이 없으면 없다고 답한다.

입력

첫 번째 줄에는 배열의 원소 개수와 쿼리의 개수를 나타내는 두 정수 $n, q$ ($1 \le n, q \le 500\,000$)가 주어진다. 두 번째 줄에는 $n$개의 정수 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$)이 주어진다. 다음 $q$개의 줄에는 각 쿼리에 대한 설명이 주어진다. 줄의 첫 번째 정수가 1이면, 다음 두 정수는 $i$와 $y$ ($1 \le i \le n, 1 \le y \le 10^9$)이며, 이는 첫 번째 유형의 쿼리를 설명한다. 그렇지 않고 첫 번째 정수가 2이면, 다음 정수는 $l$ ($1 \le l \le n$)이며, 이는 두 번째 유형의 쿼리를 설명한다.

출력

두 번째 유형의 각 쿼리에 대해, $l \le a < b < c < d$이고 $x_a < x_b < x_c < x_d$를 만족하는 모든 튜플 $(a, b, c, d)$ 중 가장 작은 $d$를 출력하거나, 그러한 튜플이 없으면 "-1"을 출력한다.

예제

입력 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

출력 1

4
5
6
-1
-1
11