Problem
Melone 想测试他的新开发 - 一个可以穿过迷宫的机器人。
机器人处于大小为 n × m 的矩形迷宫中。迷宫的每个单元格要么是空的，要么被障碍物占据。
机器人可以在相邻单元之间向左（符号“L”）、向右（符号“R”）、向上（符号“U”）或向下（符号“D”）移动。如果它是空的，机器人只能移动到一个单元格。最初，机器人在一个空笼子里。
Melone 希望机器人经过长度恰好为 k 的字典序最小循环，该循环在机器人最初所在的单元格中开始和结束。允许机器人访问任何单元格任意次数（包括起始单元格）。
机器人的路径由一个由字符“L”、“R”、“U”组成的字符串给出和“D”。比如机器人先下，再左，再右再上，那么它的路径就写成“DLRU”。
帮助 Melona 确定机器人的哪条路径恰好对应字典序最小长度的循环，或者告诉我没有这样的东西。
输入：
第一行后面跟着三个整数n、m和k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< /sup>)——迷宫尺寸和循环长度。
接下来的 n 行中的每一行都包含 m 个字符 —迷宫的描述。如果符号为“.”，则当前单元格为空。如果符号为“*”，则当前单元格被障碍物占据。如果符号是“X”，那么最初机器人在这个单元格中，并且它是空的。保证字符“X”在迷宫中只出现一次。
输出：
打印长度恰好为 k 的 Robot 按字典顺序排列的最小路径，该路径在 Robot 最初所在的单元格中开始和结束。如果不存在这样的路径，则打印“IMPOSSIBLE” （不带引号）。
示例：
<正文>
| 输入 |
输出 |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
不可能 |