E. Missing Number Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has an array of positive integers $$$a_1, \dots, a_N$$$, consisting of positive integers at most $$$N$$$. He needs to perform $$$Q$$$ operations on the array of two types:

  • $$$\texttt{1}\,~x\,~y$$$: Set $$$a_x \leftarrow y$$$.
  • $$$\texttt{2}\,~l\,~r$$$: Output any integer in the range $$$[1, N]$$$ that is not found in $$$a_l, a_{l+1}, \dots, a_r$$$.

Help answer all of Busy Beaver's queries! The input will be generated in such a way that an answer exists for all type $$$\texttt{2}$$$ queries.

Input

The first line contains two positive integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 2 \cdot 10^5$$$; $$$1 \le Q \le 2 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le N$$$).

Each of the next $$$Q$$$ lines contains three positive integers: either $$$\texttt{1}\,~x\,~y$$$ or $$$\texttt{2}\,~l\,~r$$$ ($$$1 \le x, y \le N$$$; $$$1 \le l \le r \le N$$$).

Additional constraint on the input: there is at least one type $$$\texttt{2}$$$ query, and every type $$$\texttt{2}$$$ query has an answer.

Output

For each type $$$\tt{2}$$$ query, output a single line containing the answer. If there are multiple possible answers for a query, you may output any of them.

Scoring

There are three subtasks for this problem.

  • ($$$20$$$ points) $$$N, Q \le 2000$$$.
  • ($$$30$$$ points) All queries are of type $$$\texttt{2}$$$.
  • ($$$50$$$ points) No additional constraints.
Example
Input
5 4
3 5 2 1 5
2 1 5
1 4 4
1 3 1
2 3 5
Output
4
2
Note

In the first query, the only integer from $$$1$$$ to $$$5$$$ missing from $$$[3, 5, 2, 1, 5]$$$ is $$$4$$$, so $$$4$$$ is the only possible answer.

After the second query, the array becomes $$$[3, 5, 2, 4, 5]$$$.

After the third query, the array becomes $$$[3, 5, 1, 4, 5]$$$.

The last query asks for an integer from $$$1$$$ to $$$5$$$ missing from $$$[1, 4, 5]$$$. Either $$$2$$$ or $$$3$$$ would be acceptable answers to this query.