Background

Special for beginners, ^_^

Description

有 9 个时钟，排成一个 $3\times 3$ 的矩阵。

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

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

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

现在需要用最少的移动，将 9 个时钟的指针都拨到 12 点的位置。共允许有 9 种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动 90 度。

移动    影响的时钟
 1         ABDE
 2         ABC
 3         BCEF
 4         ADG
 5         BDEFH
 6         CFI
 7         DEGH
 8         GHI
 9         EFHI  

Format

Input

9 个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。

其中，0=12点、1=3点、2=6点、3=9点。

Output

输出一个最短的移动序列，使得 9 个时钟的指针都指向 12 点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。

Samples

3 3 0 
2 2 2 
2 1 2 

4 5 8 9 

Limitation

1s, 1024KiB for each test case.