Вы очнулись в тёмной комнате и сразу поняли, что оказались в лабиринте, из которого надо выбраться! Лабиринт представляет собой прямоугольник из $$$N$$$ строк по $$$M$$$ клеток в каждой, некоторые из которых заняты стеклянными или сплошными стенами, причем весь лабиринт окружают сплошные стены. Если смотреть на карту лабиринта, то строки пронумерованы от $$$1$$$ до $$$N$$$ сверху вниз, а столбцы пронумерованы от $$$1$$$ до $$$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»), выведенными подряд. Типы действий:
Направление может принимать значения «U», «D», «R» или «L» — вверх, вниз, вправо и влево соответственно.
5 5 WWWWW WW..W WWGWW W...W WWWWW 2 3 4 2
2 2 OD BL ML ML
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
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
Иллюстрацию к первому примеру можно увидеть ниже.
