Cho dãy $A$ có độ dài $n$. Gọi $f(x,y)=[x\leq y]$, ở đây $[st]=1$ nếu mệnh đề $st$ đúng, ngược lại $[st]=0$. Dãy đặc trưng của $A$ là một dãy $B$ khác có độ dài $n-1$, trong đó $B_i=f(A_i,A_{i+1})$. Ví dụ, dãy đặc trưng của $1,3,3,1,2$ là $1,1,0,1$.

Có $q$ truy vấn với định dạng sau đây.

• $1\ x\ v$, nghĩa là bạn cần thay đổi $A_x$ thành $v$, lưu ý rằng dãy đặc trưng cũng sẽ thay đổi.
• $2\ l\ r\ v$, nghĩa là bạn cần tìm $i$ nhỏ nhất thuộc $[l,r]$ sao cho nếu thay $A_i$ bằng $v$ thì dãy đặc trưng không thay đổi, hoặc đưa ra $-1$ nếu không có $i$ nào như vậy. Lưu ý rằng truy vấn này không làm thay đổi dãy.

Hãy đưa ra câu trả lời cho tất cả các truy vấn loại $2$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n,q$ ($3\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^5$), biểu thị độ dài của dãy và số lượng truy vấn.

Dòng tiếp theo chứa $n$ số nguyên, số thứ $i$ là $A_i$ ($1\leq A_i\leq 10^9$).

Mỗi dòng trong $q$ dòng tiếp theo chứa một truy vấn, theo định dạng đã cho. Nếu loại truy vấn là $1$, thì đảm bảo $1\leq x\leq n$, $1\leq v\leq 10^9$. Nếu loại truy vấn là $2$, thì đảm bảo $1\leq l\leq r\leq n$, $1\leq v\leq 10^9$.

Dữ liệu ra

Với mỗi truy vấn loại $2$, hãy in ra một dòng, biểu thị câu trả lời cho truy vấn đó.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

-1
2
3