Время на тест - 1 секунда.
Всем хорошо известна "Игра в 15", представляющая собой 15 квадратных фишек, пронумерованных числами от 1 до 15. Фишки уложены в квадрат со стороной в 4 стороны фишки, одна позиция для фишки свободна. Если обозначить свободную позицию за *, то головоломка состоит в том, чтобы получить из произвольной начальной позиции позицию следующего вида:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 *
Единственной разрешенной операцией является обмен * с одной из соседних по ребру фишек. Операции будем кодировать буквами:
r
поменять * с фишкой, которая стоит справа от *
l
поменять * с фишкой, которая стоит слева от *
u
поменять * с фишкой, которая стоит сверху от *
d
поменять * с фишкой, которая стоит снизу от *
Например, решением головоломки
1 2 3 4 5 6 7 8 9 10 12 * 13 14 11 15
является последовательность ldr.
Не все возможные произвольные расположения фишек можно привести к требуемому виду, например, если в требуемой позиции поменять местами две фишки, то получить из такой позиции требуемую используя только описанные операции становится невозможно.
От вас требуется решить более простую головоломку "Игра в 8", в которой требуется расположить 8 фишек в виде:
1 2 3 4 5 6 7 8 *
Формат входных данных
На вход программе подается описание исходной позиции в виде строки, в которой перечислены номера фишек, разделенные пробелами в квадрате слева направо сверху вниз. Вместо свободной фишки напечатана *.
Например, позиция
1 2 3 * 4 6 7 5 8
задается строкой
1 2 3 * 4 6 7 5 8
Формат выходных данных
На выход программа должна вывести одну строку, состоящцю из букв l, r, u, d, содержащую последовательность операций, разрешающую данную головоломку, в которой одна буква соответствует перемещению одной фишки (см. выше правило кодирования операций). Если же головоломка неразрешима, то требуется вывести одно слово unsolvable.
Пример
Входные данные
2 3 4 1 5 * 7 6 8
Выходные данные
ullddrurdllurdruldr