長さ $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$ のクエリすべてに対する答えを求めよ。

入力

最初の行には $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$ の場合、$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$ 行に出力せよ。

入出力例

入力例 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