Description

Alice has a sequence $a_1,a_2,...a_n$. Now she needs Bob to support querying the mode within a range, and also support modifying a position $a_i$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, representing $a_1,...,a_n$.

The next $m$ lines each contain three integers $flag, x, y$.

If $flag=0$, it queries the mode in the range $\big[x,y\big]$. If there are multiple, output the smaller one.

If $flag=1$, it sets $a_x$ to $y$.

Output Format

For each query with $flag=0$, output one integer per line representing the answer.

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

1
2

Hint

For 100% of the testdata, $n, m \le 1000$.

For all query operations, $x \le y$.

At any time $0 < a_i \le 10^9$.

Translated by ChatGPT 5