The Clock Puzzle

There is a 3 × 3 grid of clocks labeled A through I as shown below:

|-------|   |-------|   |-------|
|       |   |       |   |   |   |
|---o   |   |---o   |   |   o   |
|       |   |       |   |       |
|-------|   |-------|   |-------|
    A           B           C
|-------|   |-------|   |-------|
|       |   |       |   |       |
|   o   |   |   o   |   |   o   |
|   |   |   |   |   |   |   |   |
|-------|   |-------|   |-------|
D           E           F
|-------|   |-------|   |-------|
|       |   |       |   |       |
|   o   |   |   o---|   |   o   |
|   |   |   |       |   |   |   |
|-------|   |-------|   |-------|
G           H           I

</p>

Each clock shows one of the times: 12, 3, 6, or 9. We can represent these times modulo 4 as follows: 12 as 0, 3 as 1, 6 as 2, and 9 as 3. There are 9 possible moves, numbered 1 through 9. Each move rotates certain clocks a total of \(90^\circ\) clockwise. A move may be applied 0 to 3 times. The moves affect the clocks as follows:

Move	Affected Clocks
1	A, B, D, E
2	A, B, C
3	B, C, E, F
4	A, D, G
5	B, D, E, F, H
6	C, F, I
7	D, E, G, H
8	G, H, I
9	E, F, H, I

The objective is to find a minimal sequence of moves that makes all the clocks point to 12 (i.e. state 0). The output should be the list of move numbers (each repeated as many times as it is applied) in increasing order, separated by single spaces. For example, if move 4 is applied once and move 5 is applied once, the output should be 4 5 (not necessarily the order in which the moves were applied).

Example:

Input:
9 9 12
6 6 6
6 3 6
Output:
4 5 8 9

</p>

In the above example, applying move 4, then 5, followed by 8 and 9 (in some order) causes all clocks to point to 12. The answer is then reported as the sorted sequence: 4 5 8 9.

inputFormat

The input consists of 3 lines. Each line contains 3 integers separated by spaces. Each integer is one of {12, 3, 6, 9} and represents the current position of a clock. The clocks are given in row-major order corresponding to labels A, B, C, D, E, F, G, H, I.

outputFormat

Output the sequence of moves (numbers between 1 and 9) that will set all clocks to 12. The moves should be printed in increasing order, separated by a single space. If no moves are needed, output an empty line.

sample

9 9 12
6 6 6
6 3 6

4 5 8 9