Se te da una secuencia $A$ de longitud $n$. Sea $f(x,y)=[x\leq y]$, donde $[st]=1$ si la declaración $st$ es verdadera, de lo contrario $[st]=0$. La secuencia característica de $A$ es otra secuencia $B$ de longitud $n-1$, donde $B_i=f(A_i,A_{i+1})$. Por ejemplo, la secuencia característica de $1,3,3,1,2$ es $1,1,0,1$.

Hay $q$ consultas en el siguiente formato.

• $1\ x\ v$, que significa que debes cambiar $A_x$ por $v$; nota que la secuencia característica también cambiará.
• $2\ l\ r\ v$, que significa que debes encontrar el menor $i\in [l,r]$ tal que si reemplazas $A_i$ con $v$, la secuencia característica no cambiará, o devolver $-1$ si no existe tal $i$. Nota que esta consulta no modificará la secuencia.

Por favor, proporciona la respuesta a todas las consultas de tipo $2$.

Entrada

La primera línea contiene dos enteros $n,q$ ($3\leq n\leq 5\times 10^5, 1\leq q\leq 5\times 10^5$), que denotan la longitud de la secuencia y el número de consultas.

La siguiente línea contiene $n$ enteros, el $i$-ésimo de los cuales denota $A_i$ ($1\leq A_i\leq 10^9$).

Cada una de las siguientes $q$ líneas contiene una consulta, en el formato dado anteriormente. Si el tipo de consulta es $1$, entonces se garantiza que $1\leq x\leq n, 1\leq v\leq 10^9$. Si el tipo de consulta es $2$, entonces se garantiza que $1\leq l\leq r\leq n, 1\leq v\leq 10^9$.

Salida

Para cada consulta de tipo $2$, imprime una línea, que denota la respuesta a la consulta.

Ejemplos

Entrada 1

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

Salida 1

-1
2
3