CF769C.Cycle In Maze

The Robot is in a rectangular maze of size n × m. Each cell of the maze is either empty or occupied by an obstacle. The Robot can move between neighboring cells on the side left (the symbol "L"), right (the symbol "R"), up (the symbol "U") or down (the symbol "D"). The Robot can move to the cell only if it is empty. Initially, the Robot is in the empty cell.

Your task is to find lexicographically minimal Robot's cycle with length exactly k, which begins and ends in the cell where the Robot was initially. It is allowed to the Robot to visit any cell many times (including starting).

Consider that Robot's way is given as a line which consists of symbols "L", "R", "U" and "D". For example, if firstly the Robot goes down, then left, then right and up, it means that his way is written as "DLRU".

In this task you don't need to minimize the length of the way. Find the minimum lexicographical (in alphabet order as in the dictionary) line which satisfies requirements above.

机器人位于一个 $n \times m$ 的矩形迷宫中。迷宫的每个格子要么为空，要么被障碍物占据。机器人可在相邻的四个方向（左：符号 "L"、右：符号 "R"、上：符号 "U"、下：符号 "D"）之间移动。机器人仅能移动到空格子中。初始时，机器人位于某个空格子中。

你的任务是找出一个长度恰好为 $k$ 的、字典序最小的机器人环路（cycle），该环路起始和终止于机器人初始所在的格子。允许机器人多次访问任意格子（包括起始格子）。

将机器人的路径表示为一个由字符 "L"、"R"、"U" 和 "D" 组成的字符串。例如，若机器人先向下、再向左、再向右、最后向上，则其路径记为 "DLRU"。

本题中你无需最小化路径长度，而应找出满足上述条件的字典序（即按字典顺序，如同查字典）最小的字符串。

The first line contains three integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — the size of the maze and the length of the cycle.

Each of the following n lines contains m symbols — the description of the maze. If the symbol equals to "." the current cell is empty. If the symbol equals to "*" the current cell is occupied by an obstacle. If the symbol equals to "X" then initially the Robot is in this cell and it is empty. It is guaranteed that the symbol "X" is found in the maze exactly once.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq 10^6$）——分别表示迷宫的尺寸和循环的长度。

接下来的 $n$ 行，每行包含 $m$ 个字符，用于描述迷宫：

• 若字符为 .，则当前格子为空；
• 若字符为 *，则当前格子被障碍物占据；
• 若字符为 X，则机器人初始时位于该格子，且该格子为空。
  保证迷宫中恰好出现一次字符 X。

Print the lexicographically minimum Robot's way with the length exactly k, which starts and ends in the cell where initially Robot is. If there is no such way, print "IMPOSSIBLE"(without quotes).

输出字典序最小的机器人路径，其长度恰好为 $k$，且起点与终点均为机器人初始所在格子。若不存在这样的路径，则输出 "IMPOSSIBLE"（不带引号）。

In the first sample two cyclic ways for the Robot with the length 2 exist — "UD" and "RL". The second cycle is lexicographically less.

In the second sample the Robot should move in the following way: down, left, down, down, left, left, left, right, right, right, up, up, right, up.

In the third sample the Robot can't move to the neighboring cells, because they are occupied by obstacles.

在第一个样例中，机器人存在两条长度为 2 的循环路径——“UD” 和 “RL”。其中第二个循环字典序更小。

在第二个样例中，机器人应按如下方式移动：下、左、下、下、左、左、左、右、右、右、上、上、右、上。

在第三个样例中，机器人无法移动到相邻的格子，因为这些格子被障碍物占据。