Description

Consider nine clocks arranged in a $3 \times 3$ grid:

|-------|   |-------|   |-------|
|       |   |       |   |   |   |
|---o   |   |---o   |   |   o   |
|       |   |       |   |       |
|-------|   |-------|   |-------|
    A           B           C

|-------|   |-------|   |-------|
|       |   |       |   |       |
|   o   |   |   o   |   |   o   |
|   |   |   |   |   |   |   |   |
|-------|   |-------|   |-------|
    D           E           F

|-------|   |-------|   |-------|
|       |   |       |   |       |
|   o   |   |   o---|   |   o   |
|   |   |   |       |   |   |   |
|-------|   |-------|   |-------|
    G           H           I

The goal is to find a shortest sequence of moves that sets all hands to $12$ o'clock. The table below lists $9$ different methods of rotating hands; each method is called a move. Applying moves $1 \sim 9$ rotates the hands of the indicated clocks by $90$ degrees clockwise.

For example:

9 9 12       9 12 12        9 12 12        12 12 12        12 12 12
6 6 6   5 -> 9  9  9   8 -> 9  9  9   4 -> 12  9  9   9 -> 12 12 12
6 3 6        6  6  6        9  9  9        12  9  9        12 12 12

But this might not be the correct method; see below.

Input Format

Three lines, each containing three positive integers, giving the initial time of each clock (the meaning of the numbers is the same as in the example above).

Output Format

A single line containing the shortest sequence of moves that sets all hands to $12$ o'clock, listed in order and separated by single spaces.

If there are multiple solutions, output the lexicographically smallest one. (For example, 5 2 4 6 is lexicographically smaller than 9 3 1 1.)

9 9 12
6 6 6
6 3 6 

4 5 8 9

Hint

Problem translation from NOCOW.

USACO Training Section 1.4.

Translated by ChatGPT 5