Ladders and Queries

A ladder has $N$ vertical bars, numbered from $1$ to $N$ from left to right. Heights where horizontal rungs may be placed are numbered from $1$ to $2N-2$ from top to bottom. Initially, there are no rungs.

To traverse the ladder, start at the top of one vertical bar and move downward. Whenever you encounter a horizontal rung connected to the current bar, follow the rung to the adjacent bar, then continue moving downward. Repeat this process until you reach the bottom of the ladder.

You may perform the following two operations:

• $1\ h\ x$: Toggle the rung joining bars $x$ and $x+1$ at height $h$. Create it if it is absent, or erase it if it is present. $(1 \leq h \leq 2N-2, 1 \leq x \leq N-1)$
• $2\ x$: Start at the top of bar $x$ and follow the ladder downward. Determine the number of the bar reached at the bottom. This operation does not change the ladder.

Two rungs at the same height may not share a bar. Therefore, this condition must still hold after a type-$1$ operation creates a rung. If $N=1$, no rung can be placed and no type-$1$ operation is allowed.

You are given $N$ target pairs $(a_1,b_1),(a_2,b_2),\cdots,(a_N,b_N)$. Perform exactly $N$ type-$2$ operations in order so that the $i$-th type-$2$ operation starts at bar $a_i$ and ends at bar $b_i$. You may use at most $6N$ type-$1$ operations over the entire sequence of operations.

The input is given in the following format:

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

Each case is given in the following format:

$N$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_N\ b_N$

$T$ is the number of test cases. The $i$-th target pair is $(a_i,b_i)$.

For each test case, first print the total number of operations $K$. Then print the $K$ operations in order, one per line. Each operation has the form $1\ h\ x$ or $2\ x$.

There must be exactly $N$ type-$2$ operations. The $i$-th must start on bar $a_i$ and end on bar $b_i$. There may be at most $6N$ type-$1$ operations. If there are multiple solutions, print any of them.

• $1 \leq T \leq 10\,000$.
• $1 \leq N \leq 2\,000$.
• $1 \leq a_i,b_i \leq N$ ($1 \leq i \leq N$).
• The sum of $N$ over all test cases is at most $10\,000$.