시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB113220.000%

문제

Вы очнулись в темной комнате. Кто вы? Как здесь оказались? К сожалению, вы ничего не помните. В вашей комнате оказались стены двух типов --- сплошные и стеклянные. Вы поняли --- вас поместили в лабиринт, из которого надо выбраться! Лабиринт представляет собой прямоугольник $N \times M$ клеток, некоторые из которых заняты стеклянными или сплошными стенами, причем весь лабиринт окружают сплошные стены. Но одна из клеток является выходом.

Немного побродив по комнате, вы обнаружили ящик, в котором лежит странное устройство. Оказалось, что это портальная пушка, и она предназначена для установки на стене порталов одного из двух цветов --- оранжевого или синего. В каждый момент времени может быть не более одного портала каждого цвета, поэтому, когда устройство выставляет новый портал, старый портал того же цвета исчезает. Изначально порталов нет.

Стоя в клетке, вы можете выстрелить портальной пушкой в одном из четырех направлений, при этом портал создастся на ближайшей в этом направлении стороне сплошной стены. Если вы попробуете поставить портал на стороне стены, где уже стоит какой-то портал, то ничего не изменится, но будет считаться, что портальная пушка сработала.

Также вы можете передвигаться по лабиринту по любым свободным клеткам, двигаясь в одном из четырёх направлений и входить в находящийся рядом с вами портал --- при этом он должен находиться на видимой вами стороне стены в соседней с вами клетке. В таком случае вы мгновенно оказываетесь возле второго портала. Если портал ведет в стеклянную стену, то вы погибнете.

Вы опасаетесь, что портальная пушка может выйти из строя, поэтому хотите пройти лабиринт, используя ее как можно меньше раз. Напишите программу, которая рассчитает минимально возможное количество использований устройства, позволяющее вам выйти из лабиринта.

입력

В первой строке входных данных через пробел записаны два целых числа $N$ и $M$ ($3 \leq N, M \leq 1000$) --- число строк и столбцов клеток в лабиринте.

В каждой из следующих $N$ строк записаны $M$ символов, описывающих лабиринт. Символ <<W>> описывает сплошную стену, символ <<G>> --- стеклянную, а символ <<.>> --- свободную клетку. Гарантируется, что все граничные клетки заняты сплошной стеной.

В следующих двух строках записаны по два числа $r_S$, $c_S$, $r_E$, $c_E$ ($2 \leq r_S, r_E \leq N - 1$; $2 \leq c_S, c_E \leq M - 1$) --- номера строк и столбцов стартовой клетки, и клетки с выходом соответственно. Гарантируется, что эти клетки являются свободными. Нумерация клеток начинается с единицы с левого верхнего угла.

출력

Если пути до выхода даже с портальной пушкой не существует, в единственной строке выведите <<-1 -1>> (без кавычек). Иначе, в первой строке выведите два числа $P$ и $S$ --- количество выстрелов портальной пушки и число пройденных шагов соответственно. Вам требуется минимизировать только число $P$, количество шагов не должно превосходить $2 \cdot n \cdot m$.

В следующих $P + S$ строках выведите последовательность ваших действий. Каждое действие описывается двумя символами, типом действия (<<M>>, <<O>> или <<B>>) и его направлением (<<U>>, <<D>>, <<R>> или <<L>>), выведенными подряд. Типы действий:

  • <<M>> --- передвинуться на одну клетку в выбранном направлении. Вы не можете идти в клетку, в которой находится стена, на которой с вашей стороны нет портала.
  • <<O>> --- поставить оранжевый портал на ближайшей сплошной стене в выбранном направлении.
  • <<B>> --- поставить синий портал на ближайшей сплошной стене в выбранном направлении.

Направление может принимать значения <<U>>, <<D>>, <<R>> или <<L>> --- вверх, вниз, вправо и влево соответственно.

예제 입력 1

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

예제 출력 1

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

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

예제 출력 3

4 3
OR
BU
MU
BD
MR
OL
MD

힌트

Иллюстрация к первому примеру