# 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