import sys from bisect import bisect_left, bisect_right data = sys.stdin.buffer H, W = map(int, data.readline().split()) grid = [data.readline().strip() for _ in range(H)] DR, DC = (-1, 0, 1, 0), (0, 1, 0, -1) total, U, D, L, R = 0, H, -1, W, -1 for r, row in enumerate(grid): count = row.count(b".") if count: total += count U, D = min(U, r), r L, R = min(L, row.find(b".")), max(R, row.rfind(b".")) def num(r, c): return r * W + c def direction(x, y): xr, xc, yr, yc = x // W, x % W, y // W, y % W return next(d for d in range(4) if yr - xr == DR[d] and yc - xc == DC[d]) def border(): return ([num(U, c) for c in range(L, R)] + [num(r, R) for r in range(U, D)] + [num(D, c) for c in range(R, L, -1)] + [num(r, L) for r in range(D, U, -1)]) def inside(z, r, c): return z[0] <= r <= z[1] and z[2] <= c <= z[3] def rect_count(z): u, d, l, r = z if u > d or l > r: return 0 if l == il and r == ir: return row_sum[d + 1] - row_sum[u] return col_sum[r + 1] - col_sum[l] def ray_distance(r, c, d): walls = col_walls[c] if d % 2 == 0 else row_walls[r] x = r if d % 2 == 0 else c if d in (0, 3): return x - walls[bisect_left(walls, x) - 1] return walls[bisect_right(walls, x)] - x def spiral(z, start, d, turn): r, c, got, segments, first = start // W, start % W, 0, [], True while True: def distance(): x, y = r + DR[d], c + DC[d] if not inside(z, x, y) or grid[x][y] == 35: return 0 n = x - z[0] + 1 if d == 0 else z[3] - y + 1 if d == 1 else z[1] - x + 1 if d == 2 else y - z[2] + 1 n = min(n, ray_distance(x, y, d)) if len(segments) >= 3: qr, qc, qd, qn = segments[-3] er, ec = qr + DR[qd] * qn, qc + DC[qd] * qn if d % 2 and min(qr, er) <= r <= max(qr, er): gap = (qc - c) * DC[d] if gap == 0: return -1 if gap > 0: n = min(n, gap - 1) if d % 2 == 0 and min(qc, ec) <= c <= max(qc, ec): gap = (qr - r) * DR[d] if gap == 0: return -1 if gap > 0: n = min(n, gap - 1) return n length = distance() if first and length == 0: d = (d + turn) % 4 length = distance() if length < 0: return None if length == 0: break if len(segments) >= 2 and length >= segments[-2][3]: return None segments.append((r, c, d, length)) r += DR[d] * length; c += DC[d] * length; got += length first = False; d = (d + turn) % 4 return segments if got == rect_count(z) else None used = bytearray(H * W) def trace(start, d, turn, tag): r, c, segments, count = start // W, start % W, [], 0 while True: sr, sc, length = r, c, 0 while True: x, y = r + DR[d], c + DC[d] if not (0 <= x < H and 0 <= y < W) or grid[x][y] == 35 or used[num(x, y)] == tag: break r, c, length, count = x, y, length + 1, count + 1 used[num(r, c)] = tag if length: segments.append((sr, sc, d, length)) d = (d + turn) % 4 x, y = r + DR[d], c + DC[d] if not (0 <= x < H and 0 <= y < W) or grid[x][y] == 35 or used[num(x, y)] == tag: break return segments, count def add(run, d, length): if not length: return if run and run[-1][0] == d: run[-1] = (d, run[-1][1] + length) else: run.append((d, length)) def reverse_arm(run, segments): for _, _, d, length in reversed(segments): add(run, d ^ 2, length) def forward_arm(run, segments): for _, _, d, length in segments: add(run, d, length) def emit(start, run): moves, commands = 0, [] for i, (d, length) in enumerate(run): if i and d != (run[i - 1][0] + 1) % 4: return False moves += length; commands.append(("R" if i else "F") + "F" * (length - 1)) if moves != total - 1: return False print(start // W + 1, start % W + 1, "URDL"[run[0][0] if run else 0]) print(moves); print("".join(commands)) return True def partial(arc, order): tag = order + 1 for cell in arc: used[cell] = tag fd, ld = direction(arc[0], arc[1]), direction(arc[-2], arc[-1]) if order == 0: x, cx = trace(arc[0], fd ^ 2, -1, tag); y, cy = trace(arc[-1], ld, 1, tag) else: y, cy = trace(arc[-1], ld, 1, tag); x, cx = trace(arc[0], fd ^ 2, -1, tag) if len(arc) + cx + cy != total: return False run = []; reverse_arm(run, x) for i in range(1, len(arc)): add(run, direction(arc[i - 1], arc[i]), 1) forward_arm(run, y) start = arc[0] if not x else num(x[-1][0] + DR[x[-1][2]] * x[-1][3], x[-1][1] + DC[x[-1][2]] * x[-1][3]) return emit(start, run) if U == D or L == R: length = R - L + 1 if U == D else D - U + 1 if length != total: print(-1) else: emit(num(U, L), [] if length == 1 else [(1 if U == D else 2, length - 1)]) raise SystemExit p = border(); n = len(p) is_floor = [grid[x // W][x % W] == 46 for x in p] if not all(is_floor): starts = [i for i in range(n) if is_floor[i] and not is_floor[(i - 1) % n]] if len(starts) != 1: print(-1); raise SystemExit arc, i = [], starts[0] while is_floor[i]: arc.append(p[i]); i = (i + 1) % n if len(arc) >= 2 and (partial(arc, 0) or partial(arc, 1)): raise SystemExit print(-1); raise SystemExit iu, id_, il, ir = U + 1, D - 1, L + 1, R - 1 row_walls = [] col_walls = [[-1] for _ in range(W)] for r, row in enumerate(grid): walls = [-1] for c, value in enumerate(row): if value == 35: walls.append(c) col_walls[c].append(r) walls.append(W) row_walls.append(walls) for walls in col_walls: walls.append(H) row_sum = [0] for r in range(H): row_sum.append(row_sum[-1] + grid[r][il:ir + 1].count(b".")) col_sum = [0] for c in range(W): col_sum.append(col_sum[-1] + sum(grid[r][c] == 46 for r in range(iu, id_ + 1))) for k in range(n): A, B = p[(k + 1) % n], p[k] ar, ac, br, bc = A // W, A % W, B // W, B % W if ar == br: q = max(ac, bc); left, right = (iu, id_, il, q - 1), (iu, id_, q, ir) xz, yz = (right, left) if ac >= q else (left, right) else: q = max(ar, br); upper, lower = (iu, q - 1, il, ir), (q, id_, il, ir) xz, yz = (lower, upper) if ar >= q else (upper, lower) fd, ld = direction(A, p[(k + 2) % n]), direction(p[(k - 1) % n], B) x, y = spiral(xz, A, fd ^ 2, -1), spiral(yz, B, ld, 1) if x is None or y is None: continue run = []; reverse_arm(run, x) for i in range(1, n): add(run, direction(p[(k + i) % n], p[(k + i + 1) % n]), 1) forward_arm(run, y) start = A if not x else num(x[-1][0] + DR[x[-1][2]] * x[-1][3], x[-1][1] + DC[x[-1][2]] * x[-1][3]) if emit(start, run): raise SystemExit print(-1)