Задача Налеее-во!

Описание

Одним погожим деньком на плацу проходили учения. Если точнее, то шла отработка тактически важных строевых приемов: команд «направо», «налево», «кругом» и «шаг вперед». Стояла пяти-градусная жара, и солдаты скучали, в отличии от работника спецслужб потенциального врага, прибывшего на плац с целью оценки боевой готовности войск. Разведчика звали Смит, и трудился он в поте лица, делая снимки настолько часто, что буквально через три часа у него закончилась пленка. Проклиная себя за безалаберность, он покинул место проведения учений и вернулся лишь через 28 минут 12 секунд, захватив на этот раз с собой все снаряжение. Внимательно изучив обстановку, Смит понял, что за прошедшее время лишь один солдат сменил свое месторасположение. Поскольку ему не хочется признаваться в провале, он решил провернуть пару интриг и списать в конечном счете нехватку снимков на пожар в одной из африканских деревень. Смит — парень изворотливый, и такого рода вещи для него не составляют труда. Единственное, что осталось узнать — двигались ли за время его отсутствия другие солдаты, ведь они могли просто вернуться на свое место в ходе сложного тактического маневра. Кроме того, начальство может спросить, сколько команд было отдано в тот интервал времени, что не отражен на пленке. Теперь перед Смитом стоит задача: узнать, за какое минимальное число команд солдат мог переместиться из одной позиции в другую. Для наглядности, представим плац прямоугольным полемразмера N · M , а солдата на нем — фигурой, занимающей три подряд идущие смежные клетки. Далее проиллюстрировано выполнение команд.

Команда «налево»

...... ......
...... ...\..
..\-/. ...|..
...... .../..
...... ......

Команда «направо»

...... ......
...... .../..
..\-/. ...|..
...... ...\..
...... ......

Команда «кругом»

....... .......
...\-/. .../-\.
....... .......
....... .......

Команда «шаг вперед»

....... ...\-/.
...\-/. .......
....... .......
....... .......

Формат входных данных

В первой строке входного файла содержатся два целых числа N и M (1 ≤ N, M ≤ 100). Далее следуют N строк по M символов каждая — описание исходного положения солдата на плаце. Формат описания аналогичен примерам выше. Символом «*» задаются препятствия — клетки, занимать которые солдат в процессе своего перемещения не может — так Смит обозначил других солдат и противопехотные мины. Далее в аналогичном формате следует описание конечное положение солдата. Гарантируется, что все препятствия остались на своих местах.

Формат выходных данных

В выходной файл выведите минимальное количество команд, которое необходимо отдать солдату, чтобы он переместился из начального положения в конечное. Если же такое перемещение невозможно, выведите в выходной файл число «−1».