Background

After successfully landing, Steve discovers a locked door on planet M.

Problem Description

The door has a mechanism with 12 knobs, each having 4 states represented by numbers 1 to 4.

Each knob can only rotate in one direction (states: 1->2->3->4->1). When a knob is rotated, it causes another specified knob to rotate once in the same direction (no chain reaction). Different states of the same knob may cause different knobs to rotate (specified in the input).

The mechanism opens when all knobs are in state 1.

Due to the age and urgency, Steve wants to open the mechanism with the minimum number of rotations. This task is assigned to you.

Input Format

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

The first integer $s_i$ on the $i$-th line represents the initial state of the $i$-th knob.

The next 4 integers $a_{i,j}, j=1,2,3,4$ indicate which knob will rotate when the $i$-th knob is in state $j$.

Output Format

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

The second line contains $n$ integers, the sequence of knob numbers to be rotated.

The solution is guaranteed to exist.

Sample Input and Output

Input Sample #1

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

Output Sample #1

6
1 2 3 4 5 6

Input Sample #2

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

Output Sample #2

6
1 1 2 3 4 5

Input Sample #3

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

Output Sample #3

1
1

Input Sample #4

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 

Output Sample #4

10
11 4 6 10 7 7 5 9 9 9 

Notes

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

Sample 4 explanation:

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

The mechanism is guaranteed to be openable.

Each test case is worth 10 points.

You will receive points for the test case if your output format is correct, the number of steps is correct, and a valid solution is provided.

Otherwise, no points will be awarded for that test case.

Data Range:

见题面 Input 部分

见题面 Output 部分