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

ля получения водительских прав Фраю необходимо продемонстрировать экзаменатору свои навыки управления автолетом. Автолет – это низко летящее транспортное средство, широко распространенное в 3000 году. При движении по прямой автолет не требует внимания водителя, автоматически избегает столкновений и соблюдает правила движения. Водитель управляет автолетом только на поворотах, задавая направление дальнейшего движения. Для сдачи экзамена Фраю необходимо проехать на прямоугольном учебном полигоне из точки А в точку Б, при этом возможно только движение в направлениях, параллельных сторонам полигона. Фраю хочется сдать экзамен, затратив минимальные усилия, и он выбирает путь из А в Б с минимальным количеством поворотов, а не самый короткий.

Во входном файле в первой строке содержатся два целых числа, разделенных пробелом – размеры полигона `N` и `M` (`1\ <\ N\ ≤\ 100`, `1\ <\ M\ ≤\ 100`). В следующей строке содержатся четыре целых числа, разделенных пробелом – координаты начальной и конечной точки `x_{A}`, `y_{A}`, `x_{Б}`, `y_{Б}` (`1\ ≤\ x_{А}\ ≤\ M`, `1\ ≤\ y_{А}\ ≤\ N`, `1\ ≤\ x_{Б}\ ≤\ M`, `1\ ≤\ y_{Б}\ ≤\ N`). Далее следует `N` строк по `M` символов в строке – план полигона. Одна клетка на плане соответствует размерам автолета. Левый нижний угол плана полигона имеет координаты `(1,1)`. Препятствие обозначается символом '#', а свободное место – символом '.' (точка). Путь из А в Б по свободным клеткам всегда существует.

В выходной файл в первой строке вывести минимальное количество поворотов `P`, а затем `P` строк c координатами клеток, в которых необходимо выполнять повороты, в виде пары чисел, разделенных пробелом. Если существует несколько путей с минимальным количеством поворотов, нужно вывести один (любой) из них.

5 5
1 5 5 1
....#
....#
....#
.#...
.#...

2
3 5
3 1