G. Get Mex Range Add Linear
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Sorry, we have had the theme of adding up integers so many times elsewhere. So we give you a different definition of addition — adding an element to a set.

You are given $$$a$$$, a sequence of $$$n$$$ sets. Initially, $$$a_i=\left\{ 0 \right\}$$$ (set only containing $$$0$$$) for all $$$1 \le i \le n$$$.

You are asked to solve $$$q$$$ queries of the following kinds.

  • $$$1\;l\;r$$$: Set $$$a_i \leftarrow a_i \cup \left\{i-l+1\right\}$$$ for all $$$l \le i \le r$$$. ($$$1 \le l \le r \le n$$$)
  • $$$2\;i$$$: Output the value of $$$\text{mex}(a_i)$$$$$$^\dagger$$$. ($$$1 \le i \le n$$$)

$$$^\dagger$$$ Given a set of nonnegative integers $$$S$$$, $$$\text{mex}(S)$$$ is defined as the smallest nonnegative integer not in $$$S$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ — the number of sets and queries. ($$$1 \le n,q \le 5\cdot 10^5$$$)

Each of the $$$q$$$ following lines contains a query. Each query is given in the format described above.

Output

For each query of type $$$2$$$, print the answer on a new line.

Example
Input
5 9
1 1 5
2 1
2 5
1 2 3
1 4 5
1 3 3
2 2
2 3
2 4
Output
2
1
3
4
2
Note

The sample input is explained as follows.

After the first query of type $$$1$$$, $$$a$$$ changes to $$$[\left\{ 0,1 \right\},\left\{ 0,2 \right\},\left\{ 0,3 \right\},\left\{ 0,4 \right\},\left\{ 0,5 \right\}]$$$.

Then, the $$$\text{mex}$$$ of $$$\left\{ 0,1 \right\}$$$ and $$$\left\{ 0,5 \right\}$$$ are $$$2$$$ and $$$1$$$ correspondingly.

After three more queries of type $$$1$$$, $$$a$$$ changes to $$$[\left\{ 0,1 \right\},\left\{ 0,1,2 \right\},\left\{ 0,1,2,3 \right\},\left\{ 0,1,4 \right\},\left\{ 0,2,5 \right\}]$$$.

Then, the $$$\text{mex}$$$ of $$$\left\{ 0,1,2 \right\}$$$, $$$\left\{ 0,1,2,3 \right\}$$$, $$$\left\{ 0,1,4 \right\}$$$ are $$$3$$$, $$$4$$$, $$$2$$$ correspondingly.