Peter决定在n×m大小的房间里铺设镶木地板,该镶木地板由尺寸为1×2的瓷砖组成。当工人们铺设镶木地板时,很明显瓷砖图案看起来不像Peter喜欢的,工人们必须重新铺设。
工人们认为,拆除整个镶木地板然后重新铺设是一项非常困难的任务,因此他们决定每小时进行一次这样的操作:拆除两块瓷砖,形成一个 2 × 2 的正方形,将它们旋转 90 度,然后将它们放回原处。
他们不知道如何使用这些操作获得所需的配置,以及这是否可能。
帮助彼得为工人制定计划或告诉他这是不可能的。该计划最多应包含 100 000 个命令。
输入
第一行包含整数 n 和 m,房间的大小(1 ≤ n,m ≤ 50)。其中至少有一个是偶数。
以下 n 行每行包含 m 个字符,描述镶木地板砖的当前配置。每个字符代表半块的位置。字符“L”、“R”、“U”和“D”分别对应于左半部、右半部、上半部和下半部。
接下来的 n 行每行包含 m 个字符,以相同的格式描述所需的配置。
输出
在第一行输出整数k,即操作次数。接下来的k行输出操作的描述。该操作由执行操作的左上半块的坐标(行和列)指定。
如果无解,则在第一行输出-1。
示例
输入 #1
2 3 ULR DLR LRU LRD
输出 #1
2 1 2 1 1
输入 #2
4 3 ULR DLR LRU LRD ULR DUU UDD DLR
输出 #2
3 3 1 3 2 2 2
注意
在第一个示例测试中,第一个操作是旋转最右边的两个图块,之后所有图块都垂直放置。第二个操作是旋转最左边的两个图块,之后我们将得到所需的配置。