描述

你正在尝试学习玩一款简单的街机跳舞游戏。游戏垫上有$4$个箭头：上（$U$）、左（$L$）、下（$D$）、右（$R$）。当歌曲播放时，屏幕上会有箭头升起，当箭头到达顶部时，你需要踩踏游戏垫上对应的箭头。踩踏不需要的箭头不会受到惩罚，但请注意，仅仅站在箭头上并不会触发它；你必须用脚实际踩踏它。游戏中的许多节奏非常快，如果不希望自己筋疲力尽，就需要正确的步法。编写一个程序，确定执行特定箭头序列的最简单方式。

我们将以八分音符为一个基本时间单位。在任何给定时间，你的左脚和右脚分别位于不同的箭头上。每个时间单位内，只有一只脚可以执行动作（改变箭头和/或踩踏）；不允许跳跃。此外，你必须保持面向前方才能看到屏幕。这限制了你可以用哪只脚踩踏哪个箭头。最后，连续用同一只脚踩踏两个箭头（“双击”）会让人筋疲力尽，因为你无法将重心转移到那只脚上。理想情况下，你希望在一连串连续的箭头中交替使用双脚。

用一只脚执行动作时，如果该脚在上一个时间单位没有执行动作，则消耗$1$单位能量。如果它在上一个时间单位执行了动作，则不改变箭头时消耗$3$单位能量，移动到相邻箭头时消耗$5$单位能量，直接移动到对面的箭头（在上和下之间，或在左和右之间）时消耗$7$单位能量。

在正常情况下，你不能将左脚放在$R$上，或将右脚放在$L$上。但是，你可以临时“交叉”：如果左脚在$U$或$D$上，你可以扭转臀部将右脚放在$L$上——但在右脚移开之前，你不能将左脚移动到不同的箭头。（想象一下如果你尝试这样做，你的腿会缠成什么样子！）同样，你也可以将左脚交叉到右脚的上面或后面。

输入

你将获得多个箭头序列，需要为它们提供脚步指导。每个序列由一行组成，包含$1$到$70$个字符，表示每个时间单位需要踩踏的箭头。可能的字符是$U$、$L$、$D$和$R$，分别代表四个箭头，或一个点（$.$），表示不需要踩踏任何箭头。假设在序列的第一个时间单位，你的左脚和右脚分别位于$L$和$R$箭头上。

最多有$100$个序列。输入以单独的一行 # 结束。

输出

对于每个输入序列，输出一个长度相同的字符串，表示每个时间单位应该执行动作的脚，或$.$表示都不执行。如果有多个消耗最少能量的解决方案，输出任意一个即可。

示例输入

LRLRLLLLRLRLRRRRLLRRLRLDU...D...UUUUDDDD

示例输出

LRLRLLLLRLRLRRRRLLRRLRLRL...R...LLLLRRRR

来源

Waterloo local 2004.01.31