你有一個長度為 $n$ 的序列 $A$。定義 $f(x,y)=[x\leq y]$，其中 $[st]=1$ 若敘述 $st$ 為真，否則 $[st]=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$：找出最小的 $i\in [l,r]$，使得若將 $A_i$ 改為 $v$，特徵序列不會改變；若無此 $i$，則輸出 $-1$。請注意此類查詢不會改變序列。

請回答所有第 $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\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

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

輸出 1

-1
2
3