题目描述

有一个 $n$ 行 $m$ 列的网格地形，每个格子要么可以通行（.），要么是障碍（#）。你从左上角 $(1,1)$ 出发，要去右下角 $(n,m)$，每步只能走到上下左右相邻的可通行格子里，不能走出边界、也不能踩在障碍上。

每一步用一个字母记录：向下走记 D，向上走记 U，向左走记 L，向右走记 R。于是一条路线就是一个由 D、L、R、U 组成的字符串。

请你找出一条步数最少的路线；如果有多条步数最少的路线，输出其中字典序最小的那条（按 ASCII 比较字符，即 D < L < R < U）。如果根本走不到，输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，只由 . 和 # 组成。

输出格式

一行：最短路线字符串；走不到时输出 $-1$。

输入输出样例 #1

输入 #1

3 3
...
...
...

输出 #1

DDRR

说明

数据范围

• 对于 $100\%$ 的数据，$2\le n,m\le 1000$。保证起点和终点都是可通行格。