题目描述

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

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

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

在一个 $3 \times 3$ 的方阵中排列着 9 个时钟（如图1所示）。目标是用最少的操作次数将所有时钟的指针调至 12 点方向。

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

• 时钟状态表示：

  • $0$ = 12 点方向
  • $1$ = 3 点方向（顺时针旋转 $90^\circ$）
  • $2$ = 6 点方向（$180^\circ$）
  • $3$ = 9 点方向（$270^\circ$）

• 允许的操作（移动）：共有 9 种不同的操作，编号为 $1$ 到 $9$。每种操作会将特定时钟组的指针顺时针旋转 $90^\circ$（具体影响的时钟位置见图2）。

输入

程序从标准输入读取数据：

• 输入为 9 个数字，表示初始状态下每个时钟的指针方向（按行优先顺序排列，即第一行从左到右，接着第二行，最后第三行）。

输出

程序向标准输出写入结果：

• 输出一个最短的、按升序排列的操作序列，使得所有时钟均回到 $12$ 点方向。
• 题目保证解唯一。

输入样例 1

3 3 0  
2 2 2  
2 1 2  

输出样例 1

4 5 8 9  

补充说明

• 操作的影响范围（假设时钟位置为 $(i,j)$，其中 $i,j \in \{1,2,3\}$）：
  • 例如，操作 $1$ 可能影响 $(1,1), (1,2), (2,1), (2,2)$ 的时钟（具体需参考图2）。
• 目标：通过最少的操作组合，使得所有时钟的指针旋转总次数模 $4$ 等于 $0$（即回到 $0$ 状态）。