问题描述

爱丽丝刚从一处地下迷宫中探险归来, 你能根据她对于自己行动路径的回忆，帮她画出迷宫地图吗?

迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步骤, 每个移动步骤可能是上下左右四个方向中的一种, 表示爱丽丝往这个方向走了一格。你需要根据这些移动步骤给出一个迷宫地图, 并满足以下条件:

1. 爱丽丝能在迷宫内的某个空地开始, 顺利的走完她回忆的所有移动步骤。
2. 迷宫内不存在爱丽丝没有走过的空地。
3. 迷宫是封闭的, 即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处 视为迷宫外, 所有不与迷宫外联通的空地都视为是迷宫内。(迷宫地图为四联通, 即只有上下左右视为联通)
4. 在满足前面三点的前提下, 迷宫的墙的数量要尽可能少。

输入格式

第一行一个正整数 $N$, 表示爱丽丝回忆的步骤数量。

接下来一行 $N$ 个英文字符, 仅包含 $UDLR$ 四种字符, 分别表示上 $(Up)$、 下 $(Down)$、左 $(Left)$、右 $(Right)$。

输出格式

请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行, 用字符 ‘$*$’ 表示墙, 用 ‘$\$’（空格）表示非墙。

你的输出需要保证以下条件:

1. 至少有一行第一个字符为 ‘$*$’ 。
2. 第一行至少有一个字符为 ‘$\$’。
3. 每一行的最后一个字符为‘$*$’ 。
4. 最后一行至少有一个字符为 ‘$*$’。

17
UUUULLLLDDDDRRRRU

 *****
*     *
* *** *
* *** *
* *** *
*     *
 *****

样例说明

爱丽丝可以把第六行第六个字符作为起点。

外墙墙墙墙墙外

墙内内内内内墙

墙内墙墙墙内墙

墙内墙墙墙内墙

墙内墙墙墙内墙

墙内内内内内墙

外墙墙墙墙墙外

评测用例规模与约定

对于所有数据, $0<N \leq 100$。