Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой что:  цикл можно обойти, посетив каждую его клетку ровно один раз, перемещаясь каждый раз вверх/вниз/вправо/влево на одну клетку;  цикл не содержит самопересечений и самокасаний, то есть две клетки цикла соседствуют по стороне тогда и только тогда, когда они соседние при перемещении вдоль цикла (самокасание по углу тоже запрещено). 

Ниже изображены несколько примеров допустимых циклов: [Image] 

Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.

В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:  «U» — сдвинуться на клетку вверх,  «R» — сдвинуться на клетку вправо,  «D» — сдвинуться на клетку вниз,  «L» — сдвинуться на клетку влево. 

Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).

Найдите искомую последовательность команд, допускается любое направление обхода цикла.


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

В первой строке входных данных записаны два целых числа n и m (3 ≤ n, m ≤ 100) — количество строк и столбцов прямоугольного клетчатого поля соответственно.

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


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

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


-----Примеры-----
Входные данные
3 3
***
*.*
*S*

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

Входные данные
6 7
.***...
.*.*...
.*.S**.
.*...**
.*....*
.******

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



-----Примечание-----

В первом тестовом примере для обхода по часовой стрелке последовательность посещенных роботом клеток выглядит следующим образом:  клетка (3, 2);  клетка (3, 1);  клетка (2, 1);  клетка (1, 1);  клетка (1, 2);  клетка (1, 3);  клетка (2, 3);  клетка (3, 3);  клетка (3, 2).

Difficulty: MEDIUM

Starter code:

Solutions:
(n, m) = map(int, input().split())
A = [0] * n
for i in range(n):
	A[i] = input()
	for j in range(m):
		if A[i][j] == 'S':
			(per1, per2) = (i, j)
(t1, t2) = (per1, per2)
(end1, end2) = (per1, per2)
while True:
	if per1 > 0 and (t1 != per1 - 1 or t2 != per2) and (A[per1 - 1][per2] == '*' or A[per1 - 1][per2] == 'S'):
		t1 = per1
		t2 = per2
		per1 -= 1
		print('U', end='')
	elif per1 < n - 1 and (t1 != per1 + 1 or t2 != per2) and (A[per1 + 1][per2] == '*' or A[per1 + 1][per2] == 'S'):
		t1 = per1
		t2 = per2
		per1 += 1
		print('D', end='')
	elif per2 > 0 and (t1 != per1 or t2 != per2 - 1) and (A[per1][per2 - 1] == '*' or A[per1][per2 - 1] == 'S'):
		t1 = per1
		t2 = per2
		per2 -= 1
		print('L', end='')
	elif per2 < m - 1 and (t1 != per1 or t2 != per2 + 1) and (A[per1][per2 + 1] == '*' or A[per1][per2 + 1] == 'S'):
		t1 = per1
		t2 = per2
		per2 += 1
		print('R', end='')
	if end1 == per1 and end2 == per2:
		break


(n, m) = map(int, input().split())
A = ['#' * (m + 2)]
for i in range(1, n + 1):
	B = ['#'] + list(input()) + ['#']
	A.append(B)
	if 'S' in B:
		C = [i, B.index('S')]
A.append('#' * (m + 2))
N = C.copy()
q = 'L'
sh = 0
while sh == 0 or N != C:
	sh += 1
	if (A[N[0] - 1][N[1]] == '*' or A[N[0] - 1][N[1]] == 'S') and q != 'D':
		N[0] -= 1
		print('U', end='')
		q = 'U'
	elif (A[N[0] + 1][N[1]] == '*' or A[N[0] + 1][N[1]] == 'S') and q != 'U':
		N[0] += 1
		print('D', end='')
		q = 'D'
	elif (A[N[0]][N[1] - 1] == '*' or A[N[0]][N[1] - 1] == 'S') and q != 'R':
		N[1] -= 1
		print('L', end='')
		q = 'L'
	elif (A[N[0]][N[1] + 1] == '*' or A[N[0]][N[1] + 1] == 'S') and q != 'L':
		N[1] += 1
		print('R', end='')
		q = 'R'


from copy import deepcopy
(n, m) = list(map(int, input().split()))
pole = []
(x, y) = (0, 0)
count = 0
for i in range(n):
	s = input()
	pole.append(s)
	for j in range(len(s)):
		if s[j] == '*':
			count += 1
		if s[j] == 'S':
			x = i
			y = j
X = [0, -1, 0, 1]
Y = [-1, 0, 1, 0]
d = dict()
d[0] = 'L'
d[1] = 'U'
d[2] = 'R'
d[3] = 'D'
(prevx, prevy) = (-1, -1)
(xbegin, ybegin) = (deepcopy(x), deepcopy(y))
s = ''
now = 0
for i in range(n):
	for j in range(m):
		for u in range(4):
			if x + X[u] >= 0 and x + X[u] < n and (y + Y[u] >= 0) and (y + Y[u] < m):
				if pole[x + X[u]][y + Y[u]] == '*' and (x + X[u] != prevx or y + Y[u] != prevy):
					(prevx, prevy) = (deepcopy(x), deepcopy(y))
					x += X[u]
					y += Y[u]
					s += d[u]
					count -= 1
					break
		if count == -1:
			break
	if count == -1:
		break
if x - 1 >= 0 and pole[x - 1][y] == 'S':
	s += 'U'
if x + 1 < n and pole[x + 1][y] == 'S':
	s += 'D'
if y - 1 >= 0 and pole[x][y - 1] == 'S':
	s += 'L'
if y + 1 < m and pole[x][y + 1] == 'S':
	s += 'R'
print(s)


def read_ints():
	return [int(x) for x in input(' ').split()]

def main():
	(n, m) = read_ints()
	field = []
	(x, y) = (None, None)
	for i in range(n):
		line = input()
		if 'S' in line:
			(x, y) = (i, line.find('S'))
		field.append(list(line))
	field[x][y] = '*'
	flag = False
	(curr_x, curr_y) = (x, y)
	delta = [(-1, 0, 'U'), (+1, 0, 'D'), (0, -1, 'L'), (0, +1, 'R')]
	(par_x, par_y) = (-1, -1)
	while True:
		if flag:
			field[curr_x][curr_y] = 'U'
		flag = True
		for (dx, dy, label) in delta:
			(next_x, next_y) = (curr_x + dx, curr_y + dy)
			if not 0 <= next_x < n:
				continue
			if not 0 <= next_y < m:
				continue
			if par_x == next_x and par_y == next_y:
				continue
			if field[next_x][next_y] == '*':
				print(label, end='', flush=True)
				(par_x, par_y) = (curr_x, curr_y)
				(curr_x, curr_y) = (next_x, next_y)
				break
		if x == curr_x and y == curr_y:
			break

def __starting_point():
	main()
__starting_point()


(y, x) = list(map(int, input().split()))
m = ['.' * (x + 2)]
e = ''
try:
	for i in range(y):
		m.append('.' + input() + '.')
		a = m[i + 1].find('S')
		if a != -1:
			b = [i + 1, a]
except:
	pass
m.append('.' * (x + 2))
a = [b[0], b[1]]
if m[a[0] - 1][a[1]] == '*':
	e += 'U'
	a = [a[0] - 1, a[1]]
elif m[a[0]][a[1] - 1] == '*':
	e += 'L'
	a = [a[0], a[1] - 1]
elif m[a[0] + 1][a[1]] == '*':
	e += 'D'
	a = [a[0] + 1, a[1]]
else:
	e += 'R'
	a = [a[0], a[1] + 1]
while a != b:
	if (m[a[0] - 1][a[1]] == '*' or m[a[0] - 1][a[1]] == 'S') and e[-1] != 'D':
		e += 'U'
		a = [a[0] - 1, a[1]]
	elif (m[a[0]][a[1] - 1] == '*' or m[a[0]][a[1] - 1] == 'S') and e[-1] != 'R':
		e += 'L'
		a = [a[0], a[1] - 1]
	elif (m[a[0] + 1][a[1]] == '*' or m[a[0] + 1][a[1]] == 'S') and e[-1] != 'U':
		e += 'D'
		a = [a[0] + 1, a[1]]
	else:
		e += 'R'
		a = [a[0], a[1] + 1]
print(e)


def next1(x, y):
	nonlocal data, ans
	data[y][x][1] = True
	if data[y][x - 1][0] == '*' and (not data[y][x - 1][1]):
		ans += 'L'
		return (x - 1, y)
	if data[y - 1][x][0] == '*' and (not data[y - 1][x][1]):
		ans += 'U'
		return (x, y - 1)
	if data[y][x + 1][0] == '*' and (not data[y][x + 1][1]):
		ans += 'R'
		return (x + 1, y)
	if data[y + 1][x][0] == '*' and (not data[y + 1][x][1]):
		ans += 'D'
		return (x, y + 1)
	return (None, None)
(n, m) = map(int, input().split())
data = []
data.append([])
for i in range(m + 2):
	data[0].append(['.', False])
for i in range(n):
	h = input()
	sd = []
	sd.append(['.', False])
	for i in range(m):
		sd.append([h[i], False])
	sd.append(['.', False])
	data.append(sd)
data.append([])
for i in range(m + 2):
	data[-1].append(['.', False])
f = True
(startx, starty) = (-1, -1)
for i in range(1, n + 1):
	if f:
		for j in range(1, m + 1):
			if data[i][j][0] == 'S':
				(startx, starty) = (j, i)
				f = False
				break
(x, y, h1, h2) = (startx, starty, startx, starty)
ans = ''
if data[y][x - 1][0] == '*' and (not data[y][x - 1][1]):
	(x, y) = (x - 1, y)
	ans += 'L'
elif data[y - 1][x][0] == '*' and (not data[y - 1][x][1]):
	(x, y) = (x, y - 1)
	ans += 'U'
elif data[y][x + 1][0] == '*' and (not data[y][x + 1][1]):
	(x, y) = (x + 1, y)
	ans += 'R'
elif data[y + 1][x][0] == '*' and (not data[y + 1][x][1]):
	(x, y) = (x, y + 1)
	ans += 'D'
while True:
	(x, y) = next1(x, y)
	if x == None and y == None:
		break
	else:
		(x1, y1) = (x, y)
if x1 - startx == 1:
	ans += 'L'
elif x1 - startx == -1:
	ans += 'R'
elif y1 - starty == 1:
	ans += 'U'
elif y1 - starty == -1:
	ans += 'D'
print(ans)


(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	s = input().split()
	a.append(s)
for i in range(n):
	for j in range(m):
		if a[i][0][j] == 'S':
			k = j
			l = i
			continue
s = 's'
x = k
y = l
if k == 0:
	k = 1
else:
	k = 0
while a[l][0][k] != 'S':
	if y > 0:
		if (a[y - 1][0][x] == '*' or a[y - 1][0][x] == 'S') and s[len(s) - 1] != 'D':
			s += 'U'
			y -= 1
	if y < n - 1:
		if (a[y + 1][0][x] == '*' or a[y + 1][0][x] == 'S') and s[len(s) - 1] != 'U':
			s += 'D'
			y += 1
	if x > 0:
		if (a[y][0][x - 1] == '*' or a[y][0][x - 1] == 'S') and s[len(s) - 1] != 'R':
			s += 'L'
			x -= 1
	if x < m - 1:
		if (a[y][0][x + 1] == '*' or a[y][0][x + 1] == 'S') and s[len(s) - 1] != 'L':
			s += 'R'
			x += 1
	if a[y][0][x] == 'S':
		k = x
		y = l
print(s[1:])