29568번 - Налеее-во! 다국어

Одним погожим деньком на плацу проходили учения. Если точнее, то шла отработка тактически важных строевых приемов: команд <<направо>>, <<налево>>, <<кругом>> и <<шаг вперед>>. Стояла пятиградусная жара, и солдаты скучали, в отличии от работника спецслужб потенциального врага, прибывшего на плац с целью оценки боевой готовности войск.

Разведчика звали Смит, и трудился он в поте лица, делая снимки настолько часто, что буквально через три часа у него закончилась пленка. Проклиная себя за безалаберность, он покинул место проведения учений и вернулся лишь через $28$ минут $12$ секунд, захватив на этот раз с собой все снаряжение.

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

Теперь перед Смитом стоит задача: узнать, за какое минимальное число команд солдат мог переместиться из одной позиции в другую. Для наглядности, представим плац прямоугольным полем размера $N \cdot M$, а солдата на нем --- фигурой, занимающей три подряд идущие смежные клетки. Далее проиллюстрировано выполнение команд.

Команда <<налево>>
......  ......
......  ...\..
..\-/.  ...|..
......  .../..
......  ......

Команда <<направо>>
......  ......
......  .../..
..\-/.  ...|..
......  ...\..
......  ......

Команда <<кругом>>
.......  .......
...\-/.  .../-\.
.......  .......
.......  .......

Команда <<шаг вперед>>
.......  ...\-/.
...\-/.  .......
.......  .......
.......  .......

Вам, как человеку проверенному, поручено войти в доверие к Смиту, решив для него эту задачу.

В первой строке входного файла содержатся два целых числа $N$ и $M$ ($1 \le N, M \le 100$). Далее следуют $N$ строк по $M$ символов каждая --- описание исходного положения солдата на плаце. Формат описания аналогичен примерам выше. Символом <<*>> задаются препятствия --- клетки, занимать которые солдат в процессе своего перемещения не может --- так Смит обозначил других солдат и противопехотные мины.

Далее в аналогичном формате следует описание конечное положение солдата. Гарантируется, что все препятствия остались на своих местах.

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