33747번 - Get Mex Range Add Linear 다국어

문제

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$.

입력

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.

출력

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

제한

노트

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.