Problem: Nine Clocks

Want to try solving this problem? You can submit your code online if you log in or register.

Nine Clocks

Input File: clocks.in
Output File: clocks.out
Time Limit: 0.5 seconds

There are nine clocks in a 3-by-3 array as shown in the diagram below.

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

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

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

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, and these moves are numbered 1,2,...,9.

Each move involves selecting a subset of clocks and turning the dials 90 degrees clockwise on each of those clocks. The clocks affected by each move are listed in the table below.

Move   Affected clocks

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

Input

The input file will contain three lines of three numbers each, representing the starting positions of the dials. Each number will be 0, 1, 2 or 3, representing 12 o'clock, 3 o'clock, 6 o'clock or 9 o'clock respectively. The three numbers on each line will be separated by spaces.

Output

The output should consist of a shortest sequence of moves that returns all the dials to 12 o'clock. These moves should be output on a single line, with each move represented by an integer from 1 to 9 as explained above. The moves should be separated by spaces in the output file. If there are many possible solutions, you should output only one (any one will do).

Sample Input

The nine clocks from the illustration above correspond to the following input file:

3 3 0
2 2 2 
2 1 2

Sample Output

5 8 4 9

Explanation

The four moves 5 8 4 9 return all the dials to 12 o'clock as illustrated below.

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