Description

Xiao E likes a game called "Meow Meow." The game has a deck and $n$ stacks from which elements can be removed from the bottom. The task is to eliminate all cards according to the game rules. Initially, the deck contains $m$ cards whose patterns from top to bottom are $a_1, a_2, \dots, a_m$. There are $k$ types of patterns, numbered from $1$ to $k$. Each pattern appears an even number of times in the deck. All stacks are initially empty. The game allows two operations:

• Choose a stack and place the top card of the deck onto the top of that stack. After doing so, if the top two cards of this stack have the same pattern, they will be automatically removed.
• Choose two different stacks. If the cards at the bottoms of these two stacks have the same pattern, you may remove these two cards, and the cards that were originally just above the bottoms become the new bottoms. If the patterns are different, nothing happens.

There are $T$ levels in total. Xiao E cannot clear them. Please design a plan for each level: for every level, output an operation sequence that eliminates all the cards.

Input Format

The first line contains a positive integer $T$, the number of test cases.

Then for each of the $T$ test cases:

• The first line contains three positive integers $n, m, k$, denoting the number of stacks, the number of cards, and the number of pattern types on the cards.
• The second line contains $m$ positive integers $a_1, a_2, \dots, a_m$, representing the patterns of the cards in the deck from top to bottom.

The testdata guarantees that there is a solution.

Output Format

For each test case, output several lines.

The first line contains a positive integer $\mathrm{op}$, the number of operations. You must ensure $m \leq \mathrm{op} \leq 2 \times m$.

Then output $\mathrm{op}$ lines. Each line contains two or three positive integers separated by a single space.

• If the line has two integers $\texttt{1 s}$, perform the first operation on stack $s$.
• If the line has three integers $\texttt{2 s1 s2}$, perform the second operation on stacks $s_1$ and $s_2$.

You must ensure $1 \leq s, s_1, s_2 \leq n$ and $s_1 \neq s_2$.

1
2 4 2
1 2 1 2

5
1 1
1 1
1 2
2 1 2
1 1

Hint

• Sample 1 Explanation.

The figure below shows the initial state.

The figure below shows the state after the first two operations.

The figure below shows the state after the third and fourth operations.

The figure below shows the state after the fifth operation.

• Sample 2.

See the files $\texttt{meow/meow2.in}$ and $\texttt{meow/meow2.ans}$ in the contestants' directory.

• Constraints.

Let $S$ be the sum of $m$ over all $T$ test cases.

For all testdata, it is guaranteed that $S \leq 2 \times 10^6$, $1 \leq n \leq 300$, and $1 \leq a_i \leq k$.

::cute-table{tuack} | Test Point | $T=$ | $n$ | $k=$ | $m \leq$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim 3$ | $1001$ | $\leq 300$ | $2n-2$ | No limit | | $4\sim 6$ | $1002$ | $=2$ | $2n-1$ | ^ | | $7\sim 10$ | $3$ | $=3$ | ^ | $14$ | | $11\sim 14$ | $1004$ | ^ | ^ | No limit | | $15\sim 20$ | $1005$ | $\leq 300$ | ^ | ^ | ::cute-table{tuack}

• Scoring.

For each test case, your answer is considered correct if, after performing all operations in order, the deck is empty and all stacks are empty.

• Additional Hint.

You can determine which category a test point belongs to by the ones digit of $T$. Your output does not need to match the sample output; any valid solution earns points.

Translated by ChatGPT 5