你有一个长度为 $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