Intergalactic Sliding Puzzle
Contest: Codeforces Round 607 (Div. 1)
Difficulty rating: 3400
Tags: combinatorics, constructive algorithms, math

You are an intergalactic surgeon and you have an alien patient. For the purposes of this problem, we can and we will model this patient's body using a $$$2 \times (2k + 1)$$$ rectangular grid. The alien has $$$4k + 1$$$ distinct organs, numbered $$$1$$$ to $$$4k + 1$$$.

In healthy such aliens, the organs are arranged in a particular way. For example, here is how the organs of a healthy such alien would be positioned, when viewed from the top, for $$$k = 4$$$:

Here, the E represents empty space.

In general, the first row contains organs $$$1$$$ to $$$2k + 1$$$ (in that order from left to right), and the second row contains organs $$$2k + 2$$$ to $$$4k + 1$$$ (in that order from left to right) and then empty space right after.

Your patient's organs are complete, and inside their body, but they somehow got shuffled around! Your job, as an intergalactic surgeon, is to put everything back in its correct position. All organs of the alien must be in its body during the entire procedure. This means that at any point during the procedure, there is exactly one cell (in the grid) that is empty. In addition, you can only move organs around by doing one of the following things:

- You can switch the positions of the empty space E with any organ to its immediate left or to its immediate right (if they exist). In reality, you do this by sliding the organ in question to the empty space;
- You can switch the positions of the empty space E with any organ to its immediate top or its immediate bottom (if they exist) only if the empty space is on the leftmost column, rightmost column or in the centermost column. Again, you do this by sliding the organ in question to the empty space.

Your job is to figure out a sequence of moves you must do during the surgical procedure in order to place back all $$$4k + 1$$$ internal organs of your patient in the correct cells. If it is impossible to do so, you must say so.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 4$$$) denoting the number of test cases. The next lines contain descriptions of the test cases.

Each test case consists of three lines. The first line contains a single integer $$$k$$$ ($$$1 \le k \le 15$$$) which determines the size of the grid. Then two lines follow. Each of them contains $$$2k + 1$$$ space-separated integers or the letter E. They describe the first and second rows of organs, respectively. It is guaranteed that all $$$4k + 1$$$ organs are present and there is exactly one E.

Output format:
For each test case, first, print a single line containing either:

- SURGERY COMPLETE if it is possible to place back all internal organs in the correct locations;
- SURGERY FAILED if it is impossible.

If it is impossible, then this is the only line of output for the test case. However, if it is possible, output a few more lines describing the sequence of moves to place the organs in the correct locations.

The sequence of moves will be a (possibly empty) string of letters u, d, l or r, representing sliding the organ that's directly above, below, to the left or to the right of the empty space, respectively, into the empty space. Print the sequence of moves in the following line, as such a string.

For convenience, you may use shortcuts to reduce the size of your output. You may use uppercase letters as shortcuts for sequences of moves. For example, you could choose T to represent the string lddrr. These shortcuts may also include other shortcuts on their own! For example, you could choose E to represent TruT, etc.

You may use any number of uppercase letters (including none) as shortcuts. The only requirements are the following:

- The total length of all strings in your output for a single case is at most $$$10^4$$$;
- There must be no cycles involving the shortcuts that are reachable from the main sequence;
- The resulting sequence of moves is finite, after expanding all shortcuts. Note that the final sequence of moves (after expanding) may be much longer than $$$10^4$$$; the only requirement is that it's finite.

As an example, if T = lddrr, E = TruT and R = rrr, then TurTlER expands to:

- TurTlER
- lddrrurTlER
- lddrrurlddrrlER
- lddrrurlddrrlTruTR
- lddrrurlddrrllddrrruTR
- lddrrurlddrrllddrrrulddrrR
- lddrrurlddrrllddrrrulddrrrrr

To use shortcuts, print each one of them in a single line as the uppercase letter, then space, and then the string that this shortcut represents. They may be printed in any order. At the end of all of those, print a single line containing DONE.

Note: You still need to print DONE even if you don't plan on using shortcuts.

Your sequence does not need to be the shortest. Any valid sequence of moves (satisfying the requirements above) will be accepted.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
There are three shortcuts defined in the first sample output:

- R = SrS
- S = rr
- I = lldll

The sequence of moves is IR and it expands to:

- IR
- lldllR
- lldllSrS
- lldllrrrS
- lldllrrrrr

Example input:
2
3
1 2 3 5 6 E 7
8 9 10 4 11 12 13
11
34 45 6 22 16 43 38 44 5 4 41 14 7 29 28 19 9 18 42 8 17 33 1
E 15 40 36 31 24 10 2 21 11 32 23 30 27 35 25 13 12 39 37 26 20 3

Example output:
SURGERY COMPLETE
IR
R SrS
S rr
I lldll
DONE
SURGERY FAILED

Editorial:
The "shortcuts" thing in the output section is basically a way for you to define subroutines, i.e., you can create simpler (useful) operations, and then you can combine them into more complex operations.
Now, to solve the problem, we may represent the grid by the "circular permutation" obtained by going around the grid once, say in a clockwise order, starting from, say, the top-left corner.
Without the middle column, this circular permutation cannot be changed; we can rotate it, but that's it. Thus, to make progress, we must use the middle column. The key insight here is that moving something through the middle column corresponds to one, and only one, kind of operation:
which, on our circular permutation, corresponds to:
Notice that it simply moved $$$4$$$ a couple of places to the right.
In other words, moving through the middle corresponds to a rotation of $$$2k+1$$$ elements. Since we can also rotate the whole thing, this $$$(2k+1)$$$-rotation can be performed anywhere in our permutation.
But since $$$(2k+1)$$$-rotations and full rotations (i.e., $$$(4k+1)$$$-rotations) are both even permutations, and these are the only available moves, this means that inputs that are an odd permutation away from the target state are unsolvable! (You can also notice this right away once you realize that this problem is essentially the "sliding picture puzzle" but with even more restricted moves.)
Amazingly, the converse is true: all even permutations are solvable! This follows from the fact that we can produce a $$$3$$$-rotation from the given operations. You may want to try to come up with it yourself, so instead of giving the sequence of moves directly, I'll just give you a hint: there is a sequence of six $$$(2k+1)$$$-rotations that is equivalent to the $$$3$$$-rotation $$$(1 2 3)$$$ or $$$(1 3 2)$$$, and it only involves moving $$$1$$$, $$$2k+2$$$ and $$$2k+3$$$. (If you still can't find it, you could also write a backtracking program that finds it.)
Once we have any single $$$3$$$-rotation, it can then be applied anywhere, again using with full rotations. Also, it is a well-known fact that any even permutation is representable by a product of $$$3$$$-rotations. This means that all even permutations are solvable!
Now, determining which inputs are solvable is one thing, but actually finding the solution is a whole different beast. Fortunately, the "shortcuts" thing is here to make it a bit easier. The most important milestone is being able to come up with a sequence corresponding to a $$$3$$$-rotation; assign an uppercase letter for such an operation. After that, you will only need $$$3$$$-rotations and full rotations to solve the rest.