Рабочее место участника

Одним из популярных аттракционов в парке "Страна чудес Гудвина" является аттракцион "Поймать Минотавра". На квадратной площадке расставляются ящики в форме кубов таким образом, чтобы получился лабиринт с единственным входом-выходом. Минотавр прячется в лабиринте и притворяется спящим. После этого в лабиринт заходит игрок, изображающий Тесея. Он может ходить по всему лабиринту, кроме клетки со спящим Минотавром (если игрок пройдет через эту клетку, то Минотавр проснется и схватит его). Игрок должен запереть Минотавра в лабиринте, толкнув один из ящиков на соседнюю свободную клетку. Игрок может только толкать ящик от себя и не может двигать ящик на себя, влево или вправо от себя. Ящик можно передвинуть только один раз. Нельзя двигать ящики, составляющие внешнюю стену лабиринта. Запрещено также толкать ящик на клетку с Минотавром. После сдвигания ящика путь до выхода должен быть перекрыт только для Минотавра, а не игрока. Чем меньше площадь лабиринта, на которой оказывается заперт Минотавр, тем больший приз получает игрок.

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

В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 50`) – размер лабиринта. Далее следует `N` строк, содержащих по `N` символов – карта лабиринта. Символ '.' означает пустую клетку, символ '#' – клетку с ящиком, символ 'M' (прописная латинская буква M) – клетку с Минотавром. Клетка с Минотавром на карте может появиться ровно один раз, и до неё есть путь от входа в лабиринт. Также все клетки по краю лабиринта, кроме одной, заставлены ящиками.

Вывести номер строки и номер столбца клетки на карте лабиринта, в которой находится сдвигаемый ящик, и направление сдвига ящика ('D' – вниз, 'U' – вверх, 'R' – вправо, 'L' – влево). Если не существует ящика, который можно сдвинуть, чтобы запереть Минотавра, то вывести одно число `-1`.

5
##.##
#...#
###.#
#M..#
#####

3 3 D