Вам задано прямоугольное клетчатое поле, состоящее из 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: interview

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:])