On vous donne une séquence $A$ de longueur $n$. Soit $f(x,y)=[x\leq y]$, où $[st]=1$ si l’affirmation $st$ est vraie, sinon $[st]=0$. La séquence caractéristique de $A$ est une autre séquence $B$ de longueur $n-1$, telle que $B_i=f(A_i,A_{i+1})$. Par exemple, la séquence caractéristique de $1,3,3,1,2$ est $1,1,0,1$.

Il y a $q$ requêtes au format suivant.

• $1\ x\ v$ : vous devez changer $A_x$ en $v$ ; notez que la séquence caractéristique changera aussi.
• $2\ l\ r\ v$ : vous devez trouver le plus petit $i\in [l,r]$ tel que, si vous remplacez $A_i$ par $v$, la séquence caractéristique ne changera pas, ou bien renvoyer $-1$ s’il n’existe pas un tel $i$. Notez que cette requête ne modifie pas la séquence.

Veuillez donner la réponse à toutes les requêtes de type $2$.

Entrée

La première ligne contient deux entiers $n,q$ ($3\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^5$), indiquant la longueur de la séquence et le nombre de requêtes.

La ligne suivante contient $n$ entiers, dont le $i$-ième est $A_i$ ($1\leq A_i\leq 10^9$).

Chacune des $q$ lignes suivantes contient une requête, au format donné ci-dessus. Si le type de la requête est $1$, il est garanti que $1\leq x\leq n$, $1\leq v\leq 10^9$. Si le type de la requête est $2$, il est garanti que $1\leq l\leq r\leq n$, $1\leq v\leq 10^9$.

Sortie

Pour chaque requête de type $2$, affichez une ligne donnant la réponse à la requête.

Exemples

Entrée 1

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

Sortie 1

-1
2
3