题目描述

Mike 正在设计能玩捉迷藏的机器人。游戏场地是一个 $m\times n$ 的矩形网格，其中一些格子放有机器人。

每个机器人朝向四个方向之一：上、下、左、右。每个机器人都有视野区域。以朝下看的机器人为例：

• 下一行视野包含 1 个格子；
• 再下一行视野包含 3 个格子；
• 再下一行视野包含 5 个格子；
• 依此类推。

第 $k$ 行视野包含连续的 $2k-1$ 个格子，其中心列与机器人所在列相同。朝右、朝上、朝左的视野区域类似定义。

若机器人 $B$ 所在格子在机器人 $A$ 的视野区域内，则称 $A$ 看见 $B$。

为了开始捉迷藏游戏，场上不能存在一对机器人互相看见。也就是说，对任意一对机器人 $A,B$，至少满足：$A$ 不在 $B$ 的视野内，或 $B$ 不在 $A$ 的视野内。

Mike 每一步可以将任意一个机器人顺时针或逆时针旋转 $90^\circ$。他想尽快开始游戏，因此希望用最少的旋转次数得到一个满足条件的配置。

请你输出这样一个配置。可以证明，对任意初始配置，合法配置都存在。

输入格式

第一行包含两个整数 $m,n$，表示网格行数和列数。

接下来 $m$ 行，每行 $n$ 个字符，每个字符为：

• U：机器人朝上；
• D：机器人朝下；
• L：机器人朝左；
• R：机器人朝右；
• .：空格子。

输出格式

输出 $m$ 行，每行 $n$ 个字符，表示一个满足条件的配置。

输出配置必须由输入配置通过最少次数的旋转得到。若有多个最优答案，可以输出任意一个。

注意：Mike 只能旋转机器人，不能删除或增加机器人。因此输出中机器人的位置必须与输入完全相同。

数据范围

• $1 \le m,n \le 2000$

样例 1 输入

2 3
RDL
.U.

样例 1 输出

UDL
.R.

样例 2 输入

2 2
..
..

样例 2 输出

..
..