eolymp
bolt
Try our new interface for solving problems
Problems

Колпачок

Колпачок

Time limit 0.3 seconds
Memory limit 256 MiB

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

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

Input data

В первой строке записано два целых числа: количество строк N и количество столбцов M клеток (2 M N 1000), из которых состоит лист. Каждая из последующих N строк содержит по M символов:

  1. x (маленькая буква латинского алфавита) - закрашенная клетка.

  2. . (точка) - пустая клетка.

  3. o (маленькая буква латинского алфавита) - начальная клетка.

  4. + (плюс) - целевая клетка.

Во входных данных задана ровно одна начальная и ровно одна целевая клетка.

Output data

Вывести одно число - наименьшее количество перемещений колпачка, которые требуется сделать Пете для достижения цели. Если же в соответствии с заданными правилами нельзя достичь целевой клетки, то требуется вывести -1.

Examples

Input example #1
3 2
x+
xx
o.
Output example #1
2
Author Daniil Mysak
Source 2013 XXVI All-Ukrainian Informatics Olympiad, Lugansk, March 17 - 21, Round 2