IOI '94 - Haninge, Sweden

+-------+    +-------+    +-------+
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
+-------+    +-------+    +-------+
    A            B            C

+-------+    +-------+    +-------+
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
+-------+    +-------+    +-------+
    D            E            F

+-------+    +-------+    +-------+
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
+-------+    +-------+    +-------+  (Figure 1)
    G            H            I

There are nine clocks in a ~3 \times 3~ array (figure 1). The goal is to return all the dials to ~12~ o'clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number ~1~ to ~9~. That number will turn the dials ~90~ degrees clockwise on those clocks which are affected according to figure 2 below.

Move   Affected clocks

 1         ABDE
 2         ABC
 3         BCEF
 4         ADG
 5         BDEFH
 6         CFI
 7         DEGH
 8         GHI
 9         EFHI    (Figure 2)

Input Specification

The input gives nine numbers. These numbers give the start positions of the dials. ~0~ represents ~12~ o'clock, ~1~ represents ~3~ o'clock, ~2~ represents ~6~ o'clock, and ~3~ represents ~9~ o'clock. The example in figure 1 gives the following input data file:

3 3 0
2 2 2
2 1 2

Output Specification

The output should be the shortest sequence of moves (numbers), which returns all the dials to ~12~ o'clock. In case there are many solutions, only one is required. There is at least one solution.

Sample Input

3 3 0
2 2 2
2 1 2

Sample Output

4 5 8 9

Explanation

Each number represents a time according to the following table:

0 = 12 o'clock
1 = 3 o'clock
2 = 6 o'clock
3 = 9 o'clock
3 3 0         3 0 0         3 0 0         0 0 0         0 0 0
2 2 2   5->   3 3 3   8->   3 3 3   4->   0 3 3   9->   0 0 0
2 1 2         2 2 2         3 3 3         0 3 3         0 0 0