Patrick 想要在 KTH 的计算机房举办一场大型活动。他已经张贴了海报并发送了邀请函，看起来会有很多人参加。现在 Patrick 必须处理一个意想不到的问题：消防安全法规。在紧急情况下，人们必须能够足够快地撤离，因此机房内只允许容纳一定数量的人，而 Patrick 的活动人数似乎会超过这个限制。但 Patrick 没有放弃，他想证明如果人们表现得当，每个人仍然可以足够快地撤离。

建筑物可以用一个 $N \times M$ 的网格表示，其中一些单元格是障碍物，另一些是空地。建筑物有且仅有一个出口。这意味着网格边缘上有一个单元格是空的，其余的都是障碍物。一些空单元格里有人。在每一个时间步，一个人可以移动到与当前所在单元格相邻的空单元格中。也可以选择在这一步不移动。所有人同时移动，且在时间步结束时，没有两个人可以占据同一个单元格。当某人离开网格（通过唯一的出口）时，他们就会消失，不再与其他人员发生碰撞。

你的任务是计算让所有人撤离所需的最短时间，并指导人们以某种方式移动以实现这一目标。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($3 \le N, M \le 100$)，表示网格的行数和列数。

接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，表示网格的每一行。没有人的空单元格用 “.” 表示，有人占据的单元格用 “P” 表示，障碍物单元格用 “#” 表示。

网格边缘的所有单元格都是障碍物，只有一个除外。网格中的人数在 1 到 100 之间。

输出格式

如果所有人都不可能撤离（即有人被困在建筑物内），请输出一行 -1。

否则，请输出一行整数 $S$，表示所有人撤离所需的时间（秒）。设 $K$ 为网格中的人数。输出 $K$ 行，每行包含一个长度为 $S$ 的字符串，由字符 “U”（上）、“D”（下）、“R”（右）、“L”（左）、“.”（等待）组成。该字符串表示第 $i$ 个人应采取的行动。如果按从上到下、从左到右的顺序读取输入网格，则人员按其出现的顺序排列。当一个人离开网格后，给他们剩余时间的等待指令。

样例

输入格式 1

4 6
######
#.P..#
#P.#P#
##P###

输出格式 1

6
DDD...
.RDD..
ULLDDD
D.....

输入格式 2

3 3
##.
#P#
###

输出格式 2

-1

输入格式 3

7 27
###########################
#..........................
#####.#####.#####.#######.#
#......#........#......#..#
#...#..#..P#...P#..P#..#..#
#...#..#P.P#P..P#...#.P#..#
###########################

输出格式 3

25
URUURRRRRRRRRRRRRRRR.....
LLLULUURRRRRRRRRRRRRRRR..
LLUUURRRRRRRRRR..........
.RRUURUURRRRRRRRRRRRRRRR.
UURUURRRRRRRRRRRRRRRR....
.UULUURRRRRRRRRRRRRRRR...
.LLLUULUURRRRRRRRRRRRRRRR