Homework Ladder

At the end of class, the teacher announces that today's homework will be assigned using a ladder game. There are $N$ vertical lines on the board, numbered $1,2,\ldots,N$ from left to right. The amount of homework assigned to a student is written at the bottom of the line where they finish.

Initially, there are no horizontal rungs. The teacher adds rungs one at a time, each connecting adjacent vertical lines $i$ and $i+1$ at height $h$. Heights are measured from the top, so a smaller value of $h$ is higher up. Once added, a rung is never removed.

To play, start at the top of a vertical line and move downward. Whenever you encounter a rung connected to your current line, you must cross it to the other vertical line and then continue downward below that height. If you encounter no more rungs, you finish at the bottom of your current line.

For example, suppose a rung at height $3$ connects lines $2$ and $3$, and another at height $5$ connects lines $1$ and $2$. Starting from line $3$, you cross to line at height , then to line at height , and finish on line .

While the teacher is adding rungs, Dejavu wants to know where different starting lines lead in the current ladder. Process $Q$ queries of the following two types in the given order:

• $1\ i\ h$: Add a rung connecting vertical lines $i$ and $i+1$ at height $h$.
• $2\ x$: Find the number of the vertical line where you finish when starting at the top of line in the current ladder.

No vertical line is connected to more than one rung at the same height. Multiple rungs may have the same height if they do not share a vertical line.

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each type $2$ query, output the number of the destination vertical line on a separate line. Output answers in test case order and, within each test case, in query order. Output nothing for a test case with no type $2$ queries.

• $1\leq T\leq1000$.
• $2\leq N\leq200\,000$.
• $1\leq Q\leq200\,000$.