You are given an sequence $A$ of length $n$. Let $f(x,y)=[x\leq y]$, here $[st]=1$ if statement $st$ is true, otherwise $[st]=0$. The characteristic sequence of $A$ is another sequence $B$ of length $n-1$, where $B_i=f(A_i,A_{i+1})$. For example, the characteristic sequence of $1,3,3,1,2$ is $1,1,0,1$.

There are $q$ queries in the following format.

• $1\ x\ v$, which means that you should change $A_x$ into $v$, notice that the characteristic sequence will also change.
• $2\ l\ r\ v$, which means that you should find the smallest $i\in [l,r]$ such that if you replace $A_i$ with $v$, the characteristic sequence will not change, or output $-1$ if there are no such $i$. Notice that this query will not change the sequence.

Please, give the answer to all the queries of type $2$.

Input

The first line contains two integers $n,q$ ($3\leq n\leq 5\times 10^5, 1\leq q\leq 5\times 10^5$), denoting the length of the sequence and the number of queries.

The following line contains $n$ integers, the $i$-th of which denotes $A_i$ ($1\leq A_i\leq 10^9$).

Each of the following $q$ lines contains one query, in the format given above. If the type of the query is $1$, then it is guaranteed that $1\leq x\leq n, 1\leq v\leq 10^9$. If the type of the query is $2$, then it is guaranteed that $1\leq l\leq r\leq n, 1\leq v\leq 10^9$.

Output

For each query of type $2$, output one line, denoting the answer to the query.

Examples

Input 1

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

Output 1

-1
2
3