길이가 $n$인 수열 $A$가 주어집니다. $f(x,y)=[x\leq y]$로 정의합니다. 여기서 $[st]$는 명제 $st$가 참이면 $1$, 거짓이면 $0$입니다. 수열 $A$의 특성 수열은 길이가 $n-1$인 또 다른 수열 $B$이며, $B_i=f(A_i,A_{i+1})$입니다. 예를 들어, $1,3,3,1,2$의 특성 수열은 $1,1,0,1$입니다.

다음 형식의 $q$개의 질의가 주어집니다.

• $1\ x\ v$는 $A_x$를 $v$로 변경하는 것을 의미하며, 특성 수열도 변경됩니다.
• $2\ l\ r\ v$는 $[l,r]$에서 $A_i$를 $v$로 변경할 때 특성 수열이 변하지 않는 가장 작은 $i$를 찾거나, 그러한 $i$가 없으면 $-1$을 출력하는 것을 의미합니다. 이 질의는 수열을 변경하지 않습니다.

모든 2번 질의에 대한 답을 출력하세요.

입력

첫 번째 줄에는 두 정수 $n,q$ ($3\leq n\leq 5\times 10^5, 1\leq q\leq 5\times 10^5$)가 주어지며, 수열의 길이와 질의의 개수를 나타냅니다.

다음 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 $A_i$ ($1\leq A_i\leq 10^9$)를 나타냅니다.

이후 $q$개의 줄에는 각각 하나의 질의가 위에 주어진 형식으로 주어집니다. 질의의 타입이 $1$인 경우 $1\leq x\leq n, 1\leq v\leq 10^9$임이 보장됩니다. 질의의 타입이 $2$인 경우 $1\leq l\leq r\leq n, 1\leq v\leq 10^9$임이 보장됩니다.

출력

각 2번 질의에 대해 한 줄에 하나씩 답을 출력합니다.

예제

입력 1

3 4
1 2 3
2 1 2 4
2 1 3 3
1 2 3
2 2 3 4

출력 1

-1
2
3