Dany jest ciąg $A$ długości $n$. Niech $f(x,y)=[x\leq y]$, gdzie $[st]=1$, jeśli zdanie $st$ jest prawdziwe, w przeciwnym razie $[st]=0$. Ciąg charakterystyczny ciągu $A$ to inny ciąg $B$ długości $n-1$, w którym $B_i=f(A_i,A_{i+1})$. Na przykład ciągiem charakterystycznym ciągu $1,3,3,1,2$ jest $1,1,0,1$.

Jest $q$ zapytań w następującym formacie.

• $1\ x\ v$ – oznacza, że należy zmienić $A_x$ na $v$; zauważ, że ciąg charakterystyczny również się zmieni.
• $2\ l\ r\ v$ – oznacza, że należy znaleźć najmniejsze $i\in [l,r]$ takie, że jeśli zastąpisz $A_i$ przez $v$, to ciąg charakterystyczny się nie zmieni, lub wypisać $-1$, jeśli nie ma takiego $i$. Zauważ, że to zapytanie nie zmienia ciągu.

Proszę podać odpowiedzi na wszystkie zapytania typu $2$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n, q$ ($3\leq n\leq 5\times 10^5, 1\leq q\leq 5\times 10^5$), oznaczające długość ciągu i liczbę zapytań.

Kolejny wiersz zawiera $n$ liczb całkowitych, z których $i$-ta oznacza $A_i$ ($1\leq A_i\leq 10^9$).

Każdy z kolejnych $q$ wierszy zawiera jedno zapytanie w formacie podanym powyżej. Jeśli typ zapytania to $1$, to gwarantowane jest, że $1\leq x\leq n, 1\leq v\leq 10^9$. Jeśli typ zapytania to $2$, to gwarantowane jest, że $1\leq l\leq r\leq n, 1\leq v\leq 10^9$.

Wyjście

Dla każdego zapytania typu $2$ wypisz jeden wiersz zawierający odpowiedź na to zapytanie.

Przykład

Wejście 1

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

Wyjście 1

-1
2
3