CF1280F.Intergalactic Sliding Puzzle

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.

你是一名星际外科医生，正在为一名外星患者进行手术。在本题中，我们可以（也必须）将该患者的躯体建模为一个 $2 \times (2k + 1)$ 的矩形网格。该外星人拥有 $4k + 1$ 个互不相同的器官，编号为 $1$ 至 $4k + 1$。

在健康状态下，这些器官以特定方式排列。例如，下图展示了当 $k = 4$ 时，一名健康外星人从上方观察到的器官排布（图中 E 表示空位）：

一般地，第一行从左至右依次为器官 $1$ 至 $2k + 1$；第二行从左至右依次为器官 $2k + 2$ 至 $4k + 1$，并在其后紧接一个空位。

你患者的全部器官均完整且位于体内，但不知何故发生了错乱！作为星际外科医生，你的任务是将所有器官复位至正确位置。在整个手术过程中，所有器官必须始终保留在患者体内。这意味着：在任意时刻，网格中恰好有一个单元格为空。此外，你仅能通过以下两种操作移动器官：

• 你可以将空位 E 与它正左方或正右方的器官（若存在）交换位置；实际操作中，即把该器官滑入空位；
• 你仅当空位位于最左列、最右列或正中央列时，才可将其与它正上方或正下方的器官（若存在）交换位置；同样，实际操作即把该器官滑入空位。

你的任务是找出一连串操作步骤，使得患者体内全部 $4k + 1$ 个器官最终全部归位。若不可能实现，请明确说明。

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.

输入的第一行包含一个整数 $t$（$1 \le t \le 4$），表示测试用例的数量。接下来的若干行包含各测试用例的描述。

每个测试用例由三行组成。第一行包含一个整数 $k$（$1 \le k \le 15$），用于确定网格的大小。随后是两行，每行包含 $2k + 1$ 个用空格分隔的整数或字母 E。它们分别描述器官的第一行和第二行。保证所有 $4k + 1$ 个器官均存在，且其中恰好有一个 E。

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.

对于每个测试用例，首先输出一行，内容为以下二者之一：

• 若可以将所有内脏器官重新放回正确位置，则输出 SURGERY COMPLETE；
• 若无法做到，则输出 SURGERY FAILED。

若输出为 SURGERY FAILED，则该行为该测试用例的唯一输出。然而，若输出为 SURGERY COMPLETE，则还需额外输出若干行，用以描述将各器官放置到正确位置所需执行的一系列移动操作。

该移动序列是一个（可能为空的）由字母 u、d、l 或 r 组成的字符串，分别表示将空格正上方、正下方、正左方或正右方的器官滑入空格中。

请在下一行中，以该字符串形式输出移动序列。

为便于输出，您可以使用大写字母作为快捷方式，以缩减输出长度。例如，可定义 T 表示字符串 lddrr。这些快捷方式本身亦可包含其他快捷方式！例如，可定义 E 表示 TruT，等等。

您可以使用任意数量（包括零个）的大写字母作为快捷方式。唯一要求如下：

• 单个测试用例的所有输出字符串总长度至多为 $10^4$；
• 从主序列出发可达的快捷方式之间不能构成循环；
• 展开全部快捷方式后，最终得到的移动序列必须是有限长的。（注意：展开后的最终序列长度可能远超 $10^4$；唯一要求是其长度为有限值。）

举例说明：若 T = lddrr，E = TruT，R = rrr，则 TurTlER 的展开过程如下：

• TurTlER
• lddrrurTlER
• lddrrurlddrrlER
• lddrrurlddrrlTruTR
• lddrrurlddrrllddrrruTR
• lddrrurlddrrllddrrrulddrrR
• lddrrurlddrrllddrrrulddrrrrr

如需使用快捷方式，请将每个快捷方式单独占一行输出：先写对应的大写字母，再跟一个空格，然后写出该快捷方式所代表的字符串。这些快捷方式的输出顺序不限。在所有快捷方式输出完毕后，另起一行输出 DONE。

注意：即使您不打算使用任何快捷方式，也必须输出 DONE。

您的移动序列不必是最短的。任何满足上述要求的有效移动序列均被接受。

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

第一个样例输出中定义了三个快捷键：

• R = SrS
• S = rr
• I = lldll

移动序列为 IR，其展开过程如下：

• IR
• lldllR
• lldllSrS
• lldllrrrS
• lldllrrrrr