High School Programming League 2010/11

You have been charged with a task of creating a pipeline network in a hexagonal grid world. You have a set of hexagonal blocks available. On each block there is a specific pipeline layout. On the central hex of board there is a block with the source of water. Your goal is to maximize the length of pipes in which the water is available.

The board is in hexagonal shape and is build out of hexes, similarly to Gliński’s hexagonal chess board. The board is described by one parameter – the radius, which is defined as the smallest number of cells you have to cross in order to reach the edge of the board, starting from the middle cell. The radius of Gliński’s hexagonal chess board is 5.

Fig 1. Hexagonal board with radius 3 and corresponding order of hexes in output.

The hex edges are numbered in clockwise direction from 0 to 5. If cell B is in the direction 2 from cell A, than cell A is in the direction 5 from cell B. See Fig 2.

Fig 2. Directions of a hex.

Each block has a certain layout of pipes available on it. For example there may be a connection between edge 0 and 2 or a junction connecting edges 0, 1 and 4. Some pieces have a disjoint set of pipes on them. For example a piece may have a connection between edges 0 and 1 and another connection between edges 2 and 3. However each edge may belong only to one of those disjoint pipe sets. Full set of possible pieces is provided in the following part of this description. It is possible to rotate blocks clockwise. For instance, a block connecting edges 0, 1 and 4 will connect edges 2, 3 and 0 after it is rotated twice. The number of blocks available is equal to the number of hexes on the board minus one.

Initially there is one block placed on the central hex of the board with source of water available in direction 0. For any block A placed on the board, if a neighbor block B has water available in A’s direction and one of the set of pipes of A connects the edge A shares with B with some other edges, water becomes available in all directions belonging to that pipe set. Hence, the block in direction 0 from initial block should have a connection between its edge 3 and some other edges.

Input

At the beginning of the input there is a single positive integer i. After that, i test cases follow. Each test starts with a single positive integer r<=25, describing the radius of the board. Than the following 3*(r^2 + r) lines describe the blocks available in this test case.

Each line consists of a series of space separated characters, which either may be digits belonging to set <0,5>, semicolons (;) or full stops (.). The digits describe the edges of the block that are connected in this pipe set. Semicolon separates pipe sets when necessary. The line ends with full stop.

For example the two rows:

0 1 3 .
0 1 ; 2 3 .

Describe two blocks, out of which first one has one set of pipes, connecting edges 0, 1 and 3, while the second one has two sets of pipes – one connecting edges 0 and 1, while the other connects edges 2 and 3.

There is an empty line separating consecutive test cases.

The following blocks may appear in input:

0 1 .
0 2 .
0 3 .
0 1 2 .
0 1 3 .
0 1 4 .
0 1 2 3 .
0 1 2 4 .
0 1 3 4 .
0 1 ; 2 3 .
0 1 2 3 4 .
0 1 2 3 4 5 .
0 1 ; 2 3 ; 4 5 .

Your submissions will be judged against three sets of data.

• First set consists of 9 test cases with time limit set to 60 seconds.
• The second one consits of 16 test cases with board radius between 1 and 19 with time limit set to 90 seconds.
• Third set consits of 2 test cases with board radius equal to 25 with time limit set to 100 seconds.

Around 80% of total points can be earned by solving random cases genarated with following code.

Output

For each test case all blocks must be used. The output for a case in which board radius is r consists of 3*(r^2 + r) lines, each containing two integers c, o.

The hex on the corner of the board in direction 0 of central hex is the first hex on the board. We define an order of hexes such that next hex is always in direction 2 of the previous one. If hex A has no neighbor in direction 2 (end of the row has been reached), than the next hex after A is the hex in direction 4 of the most distant cell in direction 5 of A (beginning of the next row). The central title is omitted in this labeling. See Fig 1.

Each line of output describes one block placed on the board. First line correspond to the first hex of the board and so on. c is the index in input of the block placed on that hex. o is the number of times this block has been rotated clockwise. 0 <= o <= 5.

Please put a single empty line to separate answers to consequent cases.

Scoring

Your goal is to maximize the length of pipes in which water is available. We assume that length of pipes on each block is proportional to the number of edges it connects. For each block you will get one point for each edge with water on that block.

Providing water to a block that connects two edges will award you 2 points, while providing water to a block that connects all 6 edges will award you 6 points. If there are disjoint groups of pipes on a block each of them is calculated separately. If on a cell 0 1 ; 2 3 ; 4 5 . there is water available in 0-1 pipe group and in 2-3 pipe group but not in 4-5 pipe group, you will be awarded 4 points.

The number of points given in the ranking is scaled so that it is equal to 10 for the contestant whose solution has the highest score, and is proportionally less for all solutions with lower scores.

Please, submit at most 50 programs to this problem. All submissions starting with the 51st will be ignored.

Example

Input:
2
1
0 1 2 .
0 1 2 .
0 2 .
0 2 .
0 1 2 3 4 5 .
0 1 ; 2 3 .
 
2
0 1 2 4 .
0 2 .
0 2 .
0 2 .
0 2 .
0 2 .
0 1 2 4 .
0 3 .
0 2 .
0 3 .
0 2 .
0 3 .
0 2 .
0 1 ; 2 3 .
0 2 .
0 1 ; 2 3 ; 4 5 .
0 2 .
0 3 .
 
Output:
0 2
2 3
3 1
5 4
4 0
1 5

6 2
7 2
8 3
9 1
0 2
1 3
11 0
10 1
2 1
3 4
12 4
13 0
4 0
5 5
15 1
14 0
17 2
16 5

Scoring: 

20 + 34 = 54