Problem
Melone wants to test his new development - a robot that can move through the labyrinths.
The robot is in a rectangular maze of size n × m. Each of the cells of the labyrinth is either empty or occupied by an obstacle.
The robot can move between adjacent cells to the left (symbol "L"), right (symbol "R", up (symbol "U") or down (symbol "D"). The robot can only move to a cell if it is empty. Initially, the robot is in an empty cage.
Melone wants the robot to go through the lexicographically minimum cycle of length exactly k, which starts and ends in the cell where the robot is initially located. The robot is allowed to visit any cell any number of times (including the starting one).
The path of the robot is given by a string consisting of the characters "L", "R", "U" and "D". For example, if the robot first goes down, then left, then right and up, then its path is written as "DLRU".
Help Melona determine which path of the robot corresponds to the lexicographically minimum cycle of length exactly k, or tell me that there is no such thing.
Input:
The first line is followed by three integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6) — maze dimensions and cycle length.
Each of the next n lines contains m characters — description of the labyrinth. If the symbol is ".", then the current cell is empty. If the symbol is "*", then the current cell is occupied by an obstacle. If the symbol is equal to "X", then initially the robot is in this cell, and it is empty. It is guaranteed that the character "X" occurs exactly once in the maze.
Output:
Print the lexicographically minimal path of the Robot of length exactly k, which starts and ends in the cell where the Robot is initially located. If no such path exists, print "IMPOSSIBLE" (without quotes).
Examples:
| Input |
Output |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
IMPOSSIBLE |