Description

Alice 现在有一个序列 $a_1,a_2,...a_n$。

现在她需要 Bob 支持询问一个区间内的众数,还要支持修改一个位置的 $a_i$。

Input Format

第一行两个整数 $n,m$。

第二行 $n$ 个整数，表示 $a_1,...,a_n$。

接下来 $m$ 行，每行三个整数 $flag,x,y$。

如果 $flag=0$，表示询问 $\big[x,y\big]$ 区间内的众数，如果有多个输出较小的。

如果 $flag=1$，表示将 $a_x$ 改为 $y$。

Output Format

对于每个 $flag=0$ 的询问，每行输出一个整数表示答案。

5 3
1 1 2 2 1
0 1 4
1 2 3
0 1 4

1
2

Hint

对于 $100\%$ 的数据 $n,m \le 1000$。

对于查询操作满足 $x\le y$。

任意时刻 $0<a_i\le 10^9$。