C. Цикл в лабиринте
ограничение по времени на тест
15 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Робот находится в прямоугольном лабиринте размера n × m. Каждая из клеток лабиринта либо пустая, либо занята препятствием. Робот может передвигаться между соседними по стороне клетками влево (символ «L»), вправо (символ «R»), вверх (символ «U») или вниз (символ «D»). Робот может переместиться в клетку, только если она пустая. Изначально робот находится в пустой клетке.

Перед вами стоит задача найти лексикографически минимальный цикл Робота длины ровно k, который начинается и заканчивается в той клетке, в которой Робот находится изначально. Роботу разрешается посещать любую клетку сколько угодно раз (включая стартовую).

Считайте, что путь Робота задаётся строкой, состоящей из символов «L», «R», «U» и «D». Например, если Робот сначала пойдёт вниз, потом влево, затем вправо и вверх, то его путь записывается как «DLRU».

В этой задаче вам не нужно минимизировать длину пути. Найдите минимальную лексикографически (в алфавитном порядке, как в словаре) строку, которая удовлетворяет требованиям выше.

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

В первой строке следуют три целых числа n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — размеры лабиринта и длина цикла.

В каждой из следующих n строк следуют по m символов — описание лабиринта. Если символ равен «.», то текущая клетка пустая. Если символ равен «*», то текущая клетка занята препятствием. Если символ равен «X», то изначально Робот находится в этой клетке, и она пустая. Гарантируется, что символ «X» встречается в лабиринте ровно один раз.

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

Выведите лексикографически минимальный путь Робота длины ровно k, который начинается и заканчивается в той клетке, в которой Робот находится изначально. Если такого пути не существует, выведите «IMPOSSIBLE» (без кавычек).

Примеры
Входные данные
2 3 2
.**
X..
Выходные данные
RL
Входные данные
5 6 14
..***.
*...X.
..*...
..*.**
....*.
Выходные данные
DLDDLLLRRRUURU
Входные данные
3 3 4
***
*X*
***
Выходные данные
IMPOSSIBLE
Примечание

В первом примере для Робота существует всего два циклических пути длины 2 — «UD» и «RL». Второй вариант лексикографически меньше.

Во втором примере Робот должен выполнять перемещения в следующем порядке: вниз, влево, вниз, вниз, влево, влево, влево, вправо, вправо, вправо, вверх, вверх, вправо, вверх.

В третьем примере Робот не может переместиться ни в одну из соседних клеток, так как все они заняты препятствиями.