8-Shaped Toy
Xiao Ming has invented a new type of toy, as shown in the figure below:
This toy is an 8-shaped slide containing a total of $n + m + 1$ balls. The left side of the slide can hold exactly $n$ balls, the right side can hold exactly $m$ balls, and the middle connection point can hold exactly $1$ ball. In the figure above, $n = 10$ and $m = 10$.
These balls are identical in shape and size, but may have different colors. For convenience, we assign an integer color value to each ball to represent its color. Two balls have the same color if and only if their corresponding color values are the same.
The toy is simple to operate. Specifically, there are 4 types of operations: 1. Rotate the left circle counter-clockwise by one position; 2. Rotate the left circle clockwise by one position; 3. Rotate the right circle counter-clockwise by one position; 4. Rotate the right circle clockwise by one position.
The effect of the first operation is shown in the figure below: the $n$ balls in the left slot, together with the $1$ ball in the middle, form a circle of $n+1$ balls that is rotated counter-clockwise by one step. This causes the ball originally in the middle to be pushed into the left slot, the ball at the bottom exit of the left slot to be moved to the middle, and all other balls to move one position counter-clockwise. The $m$ balls on the right side are unaffected.
Now, Xiao Ming has provided an initial state and a target state, and hopes you can design an operation sequence (as short as possible) that transforms the initial state into the target state.
Input
This is an answer-submission problem. All input data eight1.in through eight10.in are provided in the problem directory.
For each dataset, the first line contains two integers $n$ and $m$, separated by a space. The next three lines describe the initial state, and the following three lines describe the target state.
A state is described by three lines: the first line contains $n$ space-separated integers representing the color values of the $n$ balls in the left side, given in counter-clockwise order starting from the ball marked $\alpha$ in the figure above; the second line contains $m$ space-separated integers representing the color values of the $m$ balls in the right side, also given in counter-clockwise order starting from the ball marked $\beta$ in the figure above; the third line contains $1$ integer, which is the color value of the ball in the middle.
Output
For the 10 given input files eight1.in through eight10.in, you need to submit your output files eight1.out through eight10.out respectively.
The first line of each output file contains an integer $k$, which is the length of your operation sequence. The second line contains $k$ numbers, with no separators between adjacent numbers, where each number is between 1 and 4, representing the type of that operation.
Examples
Input 1
10 10 3 2 1 3 2 1 3 2 1 2 1 3 1 1 3 3 2 3 2 3 4 4 3 2 1 3 2 1 3 2 1 1 3 1 1 3 3 2 3 2 3 2
Output 1
1 1
Input 2
2 1 3 2 0 1 3 0 1 2
Output 2
4 1324
Note
The initial and target states in Example 1 are exactly the states before and after the first operation shown in the illustration, so only one operation of type 1 is needed to reach the target state from the initial state.
Subtasks
For each dataset, we have set 9 scoring parameters $a_1, a_2, \dots, a_9$. If the contestant's output is invalid, the score is 0. Otherwise, let your answer length be $l$, and our optimal solution length be $l_{min}$. Your score will be given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $l \le l_{min}$ | 4 | $l \le l_{min} + a_4$ |
| 9 | $l \le l_{min} + a_9$ | 3 | $l \le l_{min} + a_3$ |
| 8 | $l \le l_{min} + a_8$ | 2 | $l \le l_{min} + a_2$ |
| 7 | $l \le l_{min} + a_7$ | 1 | $l \le l_{min} + a_1$ |
| 6 | $l \le l_{min} + a_6$ | 0 | $l > l_{min} + a_1$ |
| 5 | $l \le l_{min} + a_5$ |
If multiple conditions are met, the highest score is taken.
Interaction
We provide a tool called eight_check to test whether your output file is acceptable. The method to use this tool is:
./eight_check <case_no>
After calling this program, eight_check will provide the test results based on your output file, including:
Illegal exit: Unknown error;
file not found: File not found;
k too large: The $k$ in the output is too large for eight_check to test;
invalid format: The output format is invalid;
wrong answer: The output operation sequence cannot transform the initial state into the target state;
correct, your answer is x: Output is acceptable, and your output length is $x$.
Note
Please keep the input files eight*.in and your output files eight*.out safe and back them up in time to avoid accidental deletion.