F. Межгалактическая головоломка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы межгалактический хирург, и у вас есть инопланетный пациент. Для целей этой задачи мы будем моделировать тело этого пациента, используя прямоугольную сетку размером $$$2 \times (2k + 1)$$$. Инопланетянин имеет $$$4k + 1$$$ различных органов, пронумерованных целыми числами от $$$1$$$ до $$$4k + 1$$$.

У здоровых инопланетян органы устроены особым образом. Например, вот как будут расположены органы здорового инопланетянина, если смотреть сверху, для $$$k = 4$$$:

Здесь E обозначает пустое место.

В общем случае у здорового инопланетянина первая строка содержит органы от $$$1$$$ до $$$2k + 1$$$ (в порядке слева направо) и вторая строка содержит органы от $$$2k + 2$$$ до $$$4k + 1$$$ (в порядке слева направо) и пустое место после этого, в конце второй строки.

Органы вашего пациента целы, и находятся внутри его тела, но они каким-то образом перемешались! Ваша задача, как межгалактического хирурга, состоит в том, чтобы вернуть все органы свои места. Все органы пришельца должны находиться в его теле в течение всей процедуры. Это означает, что в любой момент времени во время процедуры есть ровно одна ячейка (в сетке), которая пуста. Кроме того, вы можете перемещать органы только одним из следующих способов:

  • Вы можете поменять пустую позицию E с любым органом непосредственно слева или справа от нее (если они существуют). Вы делаете это, перемещая рассматриваемый орган в пустое место;
  • Вы можете поменять пустую позицию E с любым органом непосредственно сверху или снизу от нее (если они существуют). Это можно сделать только если пустая позиция в самой левой колонке, самой правой колонке или центральной колонке. Аналогично вы перемещаете рассматриваемый орган в пустое место.

Вашей задачей является получить последовательность шагов которые вы должны сделать при операции, чтобы вернуть все $$$4k + 1$$$ органов пациента на правильные места. Если это сделать невозможно, вы должны сообщить об этом.

Входные данные

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 4$$$), количество тестовых случаев. В следующих строках находится описание тестовых случаев.

Каждый тестовый случай содержит три строки. Первая строка содержит единственное целое число $$$k$$$ ($$$1 \le k \le 15$$$), которое задает размер сетки. Затем следует две строки. Каждая из них содержит $$$2k + 1$$$ целое число или символ E. Они описывают первую и вторую строку органов, соответственно. Гарантируется, что все $$$4k + 1$$$ органов присутствуют и также был ровно один символ E.

Выходные данные

Для каждого тестового случая выведите сначала строку, содержащую:

  • SURGERY COMPLETE если возможно вернуть все органы на изначальные места по правилам;
  • SURGERY FAILED если это невозможно.

Если было невозможно, то это была единственная строка вывода для этого тестового случая. Если это возможно, выведите строку, описывающую последовательность ходов, чтобы вернуть все органы на изначальные места.

Строкой ходов (возможно пустой) является строка из символов 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 даже если вы не собираетесь использовать сокращения.

Ваша последовательность не обязана получиться кратчайшей. Любая подходящая последовательность перемещений (удовлетворяющая всем ограничениям) будет принята.

Пример
Входные данные
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
Выходные данные
SURGERY COMPLETE
IR
R SrS
S rr
I lldll
DONE
SURGERY FAILED
Примечание

Так три сокращения выглядят в первом тестовом случае:

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

Тогда последовательность команд IR раскроется в:

  • IR
  • lldllR
  • lldllSrS
  • lldllrrrS
  • lldllrrrrr