Little E fell in love with a game called "Meow Meow". This game has a pile of cards and stacks that allow bottom deletions. The task is to eliminate all the cards through the game rules.
At the beginning, there are cards in the deck, having patterns from top to bottom. All cards have a total of patterns, numbered from to . For each pattern, the number of cards with it in the deck is even. All stacks are empty at the beginning. There are two operations in this game:
- Choose a stack and put the top card of the deck on top of the stack. If after doing this, the top two cards of the stack have the same pattern, these two cards will be eliminated automatically.
- Choose two different stacks. If the cards at the bottom of the two stacks have the same pattern, these two cards can be eliminated, and the card above the bottom of the stack will become the new bottom of the stack. If different, nothing will be done.
There are a total of levels in this game, and little E has been unable to pass the level. Please help Little E design a game plan, that is, for each level of the game, give the corresponding operation sequence so that Little E can eliminate all the cards.
Input Specification
The first line contains a positive integer representing the number of data sets.
Next, there are sets of data, in each set of data:
- The first line contains three positive integers , , , which respectively represent the number of stacks, the number of cards, and the type of pattern on the card.
- The second line contains positive integers, representing , respectively, representing the pattern of the cards in the deck from top to bottom.
The input data is guaranteed to have a solution.
Output Specification
For each set of data, output several lines.
The first line contains a positive integer , indicating the number of operations. You need to guarantee that .
For the next lines, each line contains two or three positive integers separated by a space.
- If two integers 1 , do the first operation once and select stack .
- three integers 2 , do a second operation and select stacks and .
You need to guarantee that , and .
Sample Input 1
1
2 4 2
1 2 1 2
Sample Output 1
5
1 1
1 1
1 2
2 1 2
1 1
Explanation of Sample 1
Additional Samples
Additional sample cases can be found here.
Included is a grader meow_e.cpp
.
Constraints
Let be the total of across all testcases.
For all data, guarnatee , , .
Case | ||||
---|---|---|---|---|
no additional constraints | ||||
no additional constraints | ||||
Note that you can use the value of to distinguish the type of data.
Comments