题目描述

ShopiaLand 游乐园已经关闭十多年了。Eli 决心重新给孩子们带来快乐：摩天轮、碰碰车，以及过山车。为此，她说服了一位投资人出资建造新的游乐园，而设计过山车轨道路线的任务落到了她身上。

我们可以把过山车所在的区域看成一个有 $N$ 行 $M$ 列的矩形网格。每个格子要么是空格子，要么包含一个支撑轨道段的柱子。

轨道段主要有两种：直线段和 $90^\circ$ 转弯段。直线段可以水平或竖直放置。由于柱子的特殊性，每个转弯段必须有一端朝向指定方向，另一端只能朝相邻的两个方向之一。

具体地：

• 输入字符 S 表示直线段，可以放置为竖直方向 | 或水平方向 -；
• 输入字符 L 表示有一端必须朝左的转弯段，可以放置为向下转的 \ 或向上转的 /；
• 输入字符 U 表示有一端必须朝上的转弯段，可以放置为向左转的 / 或向右转的 \；
• 输入字符 R 表示有一端必须朝右的转弯段，可以放置为向上转的 \ 或向下转的 /；
• 输入字符 D 表示有一端必须朝下的转弯段，可以放置为向右转的 / 或向左转的 \。

可以存在多条互不相干的过山车轨道路线，例如儿童路线、成人路线和刺激路线等。

投资人要求：

• 每个有柱子的格子上都必须放置轨道；
• 所有轨道都必须属于某条过山车路线；
• 每条过山车路线都必须形成一个环，也就是说沿着轨道前进最终会回到出发位置；
• 空格子必须保持为空。

现在 Eli 已经有了场地规划图：对于每个有柱子的格子，给出了它应当是直线段还是某种方向受限的转弯段。请你帮助 Eli 决定每个轨道段的具体朝向，使所有要求都被满足。

输入格式

第一行输入两个整数 $N,M$，分别表示场地的行数和列数。

接下来 $N$ 行，每行是一个长度为 $M$ 的字符串，字符来自集合：

., S, L, U, R, D

其中：

• . 表示空格子；
• S 表示直线段；
• L、U、R、D 分别表示一端必须朝左、上、右、下的转弯段。

输出格式

输出 $N$ 行，每行 $M$ 个字符，表示最终的轨道规划。

若存在多个方案，请输出其中最长过山车路线尽可能长的方案。这里一条路线指一组形成环的格子序列。若仍有多个方案，输出任意一个即可。

若不存在任何合法方案，则输出一行：

IMPOSSIBLE

数据范围

• $1 \le N,M \le 500$。

评分说明

测试会按两两成组的方式进行评分。只有同一组内两个测试都在时间限制内得到正确结果，才会获得该组分数。

样例 1

输入

8 6
RSSSSL
SRSDRU
SUDSRD
UDSSRL
RLUURD
SRLRLS
SUUSSS
RSSUUL

输出

/----\
|/-\//
|\\|\\
\\||//
//\/\\
|/\/\|
|\/|||
\--/\/

样例 2

输入

2 3
DRL
US.

输出

IMPOSSIBLE

样例 3

输入

8 29
RLDDRSSLDD..DDDSSLDSSLRDRSSSD
SSSSSRDSSS..SSRSLSSRLSSSRSSLS
SSSSSSSSSSRSUSRSUSSSSSSS...SS
SRUSSSSSSSSDLSSDSUSSSSSS...SS
SDDSSSSSSULSSSSRSLSRLSSS...SS
SSSSSSSSSRSLSSUSSLUSSURU...UU
SSSSSUUSSS..SSRSSSSSSSSSSSSSD
UUULRSSUUU..UUUSSSSSSSSSSSSSU

输出

/\/\/--\/\../\/--\/--\/\/---\
|||||/\|||..||\-\||/\|||\--\|
||||||||||/-/|/-/|||||||...||
|\/||||||||/\||/-/||||||...||
|/\||||||\/||||\-\|\/|||...||
|||||||||/-/||\--/\--/\/...\/
|||||\/|||..||/-------------\
\/\/\--/\/..\/\-------------/

样例说明

样例 1 中，原题展示了输入轨道类型和输出轨道方向的一一对应关系。

样例 2 中无法让所有轨道形成闭合环。

样例 3 给出了一个可行方案。

注意：空格子也必须在输出中保留为 .。