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.


-----Input-----

The first line contains three integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10^6) — 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. 


-----Output-----

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).


-----Examples-----
Input
2 3 2
.**
X..

Output
RL

Input
5 6 14
..***.
*...X.
..*...
..*.**
....*.

Output
DLDDLLLRRRUURU

Input
3 3 4
***
*X*
***

Output
IMPOSSIBLE



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
import math
from collections import deque

def main():
	n, m, k = list(map(int, input().split()))
	grid = ["" for _ in range(n)]
	x, y = 0, 0

	for i in range(n):
		grid[i] = input()
		if 'X' in grid[i]:
			x, y = i, grid[i].index('X')

	if k % 2 == 1:
		print("IMPOSSIBLE")
		return

	dx = [1, 0, 0, -1]	
	dy = [0, -1, 1, 0]
	names = {(x1, y1): sym for x1, y1, sym in zip(dx, dy, "DLRU")}
	rev_names = {x1: y1 for x1, y1 in zip("DLRU", "URLD")}

	def ok(x, y):
		return (0 <= x < n) and (0 <= y < m) and grid[x][y] != '*'
	

	def bfs(x, y):
		MAX_DIST = (1 << 20)
		dist = [[MAX_DIST for y in range(m)] for x in range(n)]
		dist[x][y] = 0
		q = deque()
		q.append((x, y))

		while len(q) > 0:
			x, y = q.popleft()

			for x0, y0 in zip(dx, dy):
				if ok(x + x0, y + y0) and dist[x][y] + 1 < dist[x + x0][y + y0]:
					dist[x + x0][y + y0] = dist[x][y] + 1
					q.append((x + x0, y + y0))		

		return dist			

	path = []
	x_start, y_start = x, y

	dist = bfs(x_start, y_start)

	for i in range(k // 2):
		for x1, y1 in zip(dx, dy):
			if ok(x + x1, y + y1):
				path.append(names.get((x1, y1)))	
				x += x1
				y += y1
				break
		else:
			print("IMPOSSIBLE")
			return

	moves = k // 2		
	for i in range(k // 2):
		for x1, y1 in zip(dx, dy):
			if ok(x + x1, y + y1) and dist[x + x1][y + y1] <= moves:
				path.append(names.get((x1, y1)))
				x += x1
				y += y1
				moves -= 1
				break

	print("".join(x for x in path))

def __starting_point():
	main()
__starting_point()

import math
from collections import deque

def main():
	n, m, k = list(map(int, input().split()))
	grid = ["" for _ in range(n)]
	x, y = 0, 0

	for i in range(n):
		grid[i] = input()
		if 'X' in grid[i]:
			x, y = i, grid[i].index('X')

	if k % 2 == 1:
		print("IMPOSSIBLE")
		return

	dx = [1, 0, 0, -1]	
	dy = [0, -1, 1, 0]
	names = {(x1, y1): sym for x1, y1, sym in zip(dx, dy, "DLRU")}
	rev_names = {x1: y1 for x1, y1 in zip("DLRU", "URLD")}

	def ok(x, y):
		return (0 <= x < n) and (0 <= y < m) and grid[x][y] != '*'
	

	def bfs(x, y):
		MAX_DIST = (1 << 20)
		dist = [[MAX_DIST for y in range(m)] for x in range(n)]
		dist[x][y] = 0
		q = deque()
		q.append((x, y))

		while len(q) > 0:
			x, y = q.popleft()

			for x0, y0 in zip(dx, dy):
				if ok(x + x0, y + y0) and dist[x][y] + 1 < dist[x + x0][y + y0]:
					dist[x + x0][y + y0] = dist[x][y] + 1
					q.append((x + x0, y + y0))		

		return dist			

	path = []
	x_start, y_start = x, y

	dist = bfs(x_start, y_start)

	for i in range(k // 2):
		for x1, y1 in zip(dx, dy):
			if ok(x + x1, y + y1):
				path.append(names.get((x1, y1)))	
				x += x1
				y += y1
				break
		else:
			print("IMPOSSIBLE")
			return

	moves = k // 2		
	for i in range(k // 2):
		for x1, y1 in zip(dx, dy):
			if ok(x + x1, y + y1) and dist[x + x1][y + y1] <= moves:
				path.append(names.get((x1, y1)))
				x += x1
				y += y1
				moves -= 1
				break

	print("".join(x for x in path))

def __starting_point():
	main()
__starting_point()

from queue import Queue
import sys
#sys.stdin = open('input.txt')

n, m, k = [int(x) for x in input().split(' ')]

if k&1:
  print('IMPOSSIBLE')
  return

s = [None]*n
for i in range(n):
  s[i] = [None]*m
  t = input()
  for j in range(m):
    s[i][j] = t[j]
    if t[j] == 'X': x, y = j, i

def bfs(x, y):
  res = [[10000000]*m for i in range(n)]
  if s[y][x] == '*': return res
  q = Queue()
  q.put((x, y))
  step = 0

  def add(x, y):
    if res[y][x] != 10000000 or s[y][x] == '*' or step >= res[y][x]: return
    q.put((x, y))
    res[y][x] = step+1

  res[y][x] = step

  while not q.empty():
    x, y = q.get()
    step = res[y][x]
    #print('-')
    if y < n-1: add(x, y+1) #D
    if x > 0: add(x-1, y)   #L
    if x < m-1: add(x+1, y) #R
    if y > 0: add(x, y-1)   #U
  return res

res = bfs(x, y)


path = []
add = lambda s: path.append(s)
for i in range(k):
  step = k-i
  #print(step, (y, x), k-i)
  if y < n-1 and res[y+1][x] <= step: #D
    add('D')
    y = y+1
  elif x > 0 and res[y][x-1] <= step: #L
    add('L')
    x = x-1
  elif x < m-1 and res[y][x+1] <= step: #R
    add('R')
    x = x+1
  elif y > 0 and res[y-1][x] <= step: #U
    add('U')
    y = y-1
  else:
    print('IMPOSSIBLE')
    return

print(str.join('', path))


import math
from collections import deque

def main():
	n, m, k = list(map(int, input().split()))
	grid = ["" for _ in range(n)]
	x, y = 0, 0

	for i in range(n):
		grid[i] = input()
		if 'X' in grid[i]:
			x, y = i, grid[i].index('X')

	if k % 2 == 1:
		print("IMPOSSIBLE")
		return

	dx = [1, 0, 0, -1]	
	dy = [0, -1, 1, 0]
	names = {(x1, y1): sym for x1, y1, sym in zip(dx, dy, "DLRU")}
	rev_names = {x1: y1 for x1, y1 in zip("DLRU", "URLD")}

	def ok(x, y):
		return (0 <= x < n) and (0 <= y < m) and grid[x][y] != '*'
	

	def bfs(x, y):
		MAX_DIST = (1 << 20)
		dist = [[MAX_DIST for y in range(m)] for x in range(n)]
		dist[x][y] = 0
		q = deque()
		q.append((x, y))

		while len(q) > 0:
			x, y = q.popleft()

			for x0, y0 in zip(dx, dy):
				if ok(x + x0, y + y0) and dist[x][y] + 1 < dist[x + x0][y + y0]:
					dist[x + x0][y + y0] = dist[x][y] + 1
					q.append((x + x0, y + y0))		

		return dist			

	path = []
	x_start, y_start = x, y

	dist = bfs(x_start, y_start)

	for i in range(k // 2):
		for x1, y1 in zip(dx, dy):
			if ok(x + x1, y + y1):
				path.append(names.get((x1, y1)))	
				x += x1
				y += y1
				break
		else:
			print("IMPOSSIBLE")
			return

	moves = k // 2		
	for i in range(k // 2):
		for x1, y1 in zip(dx, dy):
			if ok(x + x1, y + y1) and dist[x + x1][y + y1] <= moves:
				path.append(names.get((x1, y1)))
				x += x1
				y += y1
				moves -= 1
				break

	print("".join(x for x in path))

def __starting_point():
	main()



# Made By Mostafa_Khaled

__starting_point()

#https://codeforces.com/contest/769/problem/C
import collections
lis = input().split()
n,m,k = int(lis[0]),int(lis[1]),int(lis[2])
empty = [[False for i in range(m)] for j in range(n)]
mainrow,maincol = 0,0
for i in range(n):
	s = input()
	for j in range(m):
		if(s[j]=='.'):
			empty[i][j] = True
		elif (s[j]=='X'):
			empty[i][j] = True
			mainrow = i
			maincol = j
d = [[-1 for i in range(m)] for j in range(n)]
que = collections.deque([(mainrow,maincol)])
d[mainrow][maincol] = 0
changes = [(1,0),(-1,0),(0,1),(0,-1)]
while(que):
	(x,y) = que.popleft()
	for (i,j) in changes:
		xnex = x+i
		ynex = y+j
		if(xnex>=0 and xnex<n and ynex>=0 and ynex<m and empty[xnex][ynex] and d[xnex][ynex]==-1):
			d[xnex][ynex]=d[x][y]+1
			que.append((xnex,ynex))
currrow = mainrow
currcol = maincol
lis = []
if(k%2==0):
	flag = False
	for (i,j) in changes:
		xnex = mainrow+i
		ynex = maincol+j
		if(xnex>=0 and xnex<n and ynex>=0 and ynex<m and empty[xnex][ynex]):
			flag = True
	if(flag):
		while(k):
			if(currrow+1<n and empty[currrow+1][currcol] and d[currrow+1][currcol]<k):
				lis.append('D')
				currrow+=1
			elif(currcol-1>=0 and empty[currrow][currcol-1] and d[currrow][currcol-1]<k):
				lis.append('L')
				currcol-=1
			elif(currcol+1<m and empty[currrow][currcol+1] and d[currrow][currcol+1]<k):
				lis.append('R')
				currcol+=1
			else:
				lis.append('U')
				currrow-=1
			k-=1
		if(currcol == maincol and currrow == mainrow):
			print("".join(lis))
		else:
			print("IMPOSSIBLE WHY")
	else:
		print("IMPOSSIBLE")
else:
	print("IMPOSSIBLE")