Description

There is a mechanism on the gate. It has a total of $12$ knobs, and each knob has $4$ states. The states of a knob are represented by the numbers $1$ to $4$.

Each knob can only be rotated in one direction (states: $1\rightarrow2\rightarrow3\rightarrow4\rightarrow1$). When it is rotated, it will cause another knob to rotate once as well (in the same direction, and it will not cause a chain reaction). The same knob, when in different states, may cause different knobs to rotate (given in the input).

When all knobs are rotated to state $1$, the mechanism opens.

Because the knobs have not been maintained for a long time, rotating once is difficult, and time is tight. Therefore, Steve wants to open the mechanism using the minimum number of rotations.

This task is left to you.

Input Format

There are $12$ lines, each containing $5$ integers, describing the state of the mechanism.

On line $i$, the first integer $s_i$ indicates that the initial state of the $i$-th knob is $s_i$.

The next $4$ integers $a_{i,j}, j=1,2,3,4$ indicate that when this knob is in state $j$ and is rotated, it will cause the $a_{i,j}$-th knob to rotate to the next state.

Output Format

The first line contains an integer $n$, indicating the minimum number of steps.

The second line contains $n$ integers, indicating the indices of the knobs rotated in order.

The testdata guarantees that a solution exists.

3 3 7 2 6
3 1 4 5 3
3 1 2 6 4
3 1 10 3 5
3 2 8 3 6
3 7 9 2 1
1 1 2 3 4
1 3 11 10 12
1 8 6 7 4
1 9 9 8 8
1 12 10 12 12
1 7 8 9 10

6
1 2 3 4 5 6

3 3 7 2 6
3 1 4 5 3
3 1 2 6 4
3 1 10 3 5
3 2 8 3 6
3 7 9 2 1
1 1 2 3 4
1 3 11 10 12
1 8 6 7 4
1 9 9 8 8
1 12 10 12 12
1 7 8 9 10

6
1 1 2 3 4 5

4 2 2 2 2
4 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

1
1

4 9 3 4 5 
1 9 8 12 11 
4 7 5 6 12 
3 2 2 11 2 
3 6 8 2 12 
4 8 4 2 11 
2 12 9 5 3 
4 1 1 11 1 
1 1 7 4 1 
4 11 6 12 8 
2 6 3 7 6 
4 3 9 7 10 

10
11 4 6 10 7 7 5 9 9 9 

Hint

Samples $1$ and $2$ have the same input, and both outputs are accepted.

Explanation for sample $4$:

414334 241424
Rotate knob 11 to state 3, causing knob 3 to rotate to state 1.
411334 241434
Rotate knob 4 to state 4, causing knob 11 to rotate to state 4.
411434 241444
Rotate knob 6 to state 1, causing knob 11 to rotate to state 1.
411431 241414
Rotate knob 10 to state 1, causing knob 8 to rotate to state 1.
411431 211114
Rotate knob 7 to state 3, causing knob 9 to rotate to state 2.
411431 312114
Rotate knob 7 to state 4, causing knob 5 to rotate to state 4.
411441 412114
Rotate knob 5 to state 1, causing knob 12 to rotate to state 1.
411411 412111
Rotate knob 9 to state 3, causing knob 7 to rotate to state 1.
411411 113111
Rotate knob 9 to state 4, causing knob 4 to rotate to state 1.
411111 114111
Rotate knob 9 to state 1, causing knob 1 to rotate to state 1.
111111 111111

The testdata guarantees that there is a way to open the mechanism.

Each test point is worth $10$ points.

As long as your output format is correct, you output the correct number of steps, and you provide any correct solution, you will get the score for that test point.

Otherwise, you will get $0$ points for that test point.

Constraints:

Translated by ChatGPT 5