题目描述

你在一个黑暗的房间里醒来。你不知道自己是谁，也不知道为什么会在这里。房间中的墙有两种：实体墙和玻璃墙。很快你发现，自己正身处一个需要逃脱的迷宫。

迷宫是一个 $N\times M$ 的矩形网格。部分格子是实体墙，部分格子是玻璃墙，其余格子可以自由行走。整个迷宫的边界都由实体墙组成，其中某个自由格子是出口。

你在房间里找到了一把传送门枪。它可以在墙面上放置两种颜色的传送门：橙色和蓝色。任意时刻每种颜色至多存在一个传送门；如果重新放置同色传送门，旧的同色传送门会消失。最初没有任何传送门。

当你站在一个格子中时，可以朝上、下、左、右四个方向之一开枪。传送门会出现在该方向上最近的一面实体墙的墙面上。如果你试图在已经存在传送门的墙面上再次放置传送门，则场景不会发生变化，但这仍然算作一次传送门枪的使用。

你还可以在自由格子之间进行四方向移动。如果相邻墙面上存在一个从你这一侧可进入的传送门，你可以进入它，并瞬间从另一种颜色的传送门处出现。如果出口一侧对应的是玻璃墙，那么你会死亡。

你担心传送门枪随时可能损坏，因此希望在逃出迷宫的过程中尽可能少地使用传送门枪。

请计算最少需要开枪多少次，并输出一套能够逃到出口的具体行动方案。

输入格式

第一行包含两个整数 $N,M$：

接下来 $N$ 行，每行包含 $M$ 个字符，描述迷宫：

• W：实体墙；
• G：玻璃墙；
• .：自由格子。

保证所有边界格子均为实体墙。

接下来两行各包含两个整数：

rS cS
rE cE

分别表示起点与出口的行、列编号。满足

保证起点与出口均为自由格子。格子从左上角开始，以 $1$ 为下标编号。

输出格式

如果即使使用传送门枪也无法到达出口，输出：

-1 -1

否则，第一行输出两个整数 $P,S$：

• $P$：传送门枪的使用次数；
• $S$：普通移动步数。

你只需要最小化 $P$。同时必须满足

随后输出 $P+S$ 行行动。每个行动由两个字符组成：第一个字符表示类型，第二个字符表示方向。

行动类型：

• M：向指定方向移动一步；若面对的是带有可进入传送门的墙面，则会进入传送门；
• O：向指定方向发射橙色传送门；
• B：向指定方向发射蓝色传送门。

方向：

• U：上；
• D：下；
• L：左；
• R：右。

如果存在多种最优方案，可以输出任意一种。

样例 1

5 5
WWWWW
WW..W
WWGWW
W...W
WWWWW
2 3
4 2

2 2
OD
BL
ML
ML

样例 2

7 6
WWWWWW
W..W.W
W.W..W
W.W..W
W.WG.W
W...WW
WWWWWW
2 3
2 5

2 17
ML
MD
MD
MD
MD
MR
MR
OU
ML
ML
MU
MU
MU
MU
MR
BR
MR
MR
MU

样例 3

5 5
WWWWW
W.G.W
WW.GW
W.G.W
WWWWW
2 2
4 2

4 3
OR
BU
MU
BD
MR
OL
MD

原题为第一组样例附有传送门移动示意图：

!