D. Тесей и лабиринт
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, Тесей отправился на остров Крит, чтобы победить Минотавра. Приплыв на остров, он обнаружил лабиринт, который представляет собой прямоугольное поле размера n × m, состоящее из блоков размера 1 × 1.

В каждом блоке имеется кнопка, разворачивающая все блоки по часовой стрелке на 90 градусов. Каждый блок поворачивается вокруг своего центра, расположение блоков в таблице при этом не меняется. Помимо кнопки, в каждом блоке есть несколько (возможно, 0) дверей. За одну минуту Тесей может либо перейти в соседний по стороне блок, либо нажать кнопку и привести в действие механизм по повороту всех блоков по часовой стрелке на 90 градусов. Из блока A можно перейти в соседний блок B тогда и только тогда, когда у блока A есть дверь, ведущая в блок B, а у блока B есть дверь, ведущая в блок A. Тесей уже обнаружил вход в лабиринт и оказался в блоке (xT, yT), то есть в блоке, расположенном в ряду xT и столбце yT. Тесей слышал, что Минотавр прячется в блоке (xM, yM), и хочет узнать минимальное количество минут, через которое он сможет добраться до чудовища.

Герою не к лицу решать задачи по программированию, поэтому он просит вас помочь ему.

Входные данные

В первой строке входных данных следуют два числа n и m (1 ≤ n, m ≤ 1000) — количество строк и столбцов в лабиринте соответственно.

В каждой из последующих n строк содержится по m символов, описывающих соответствующий ряд лабиринта. Рассмотрим возможные варианты символов:

  • «+» означает, что этот блок имеет 4 двери (в каждый из соседних блоков);
  • «-» означает, что этот блок имеет 2 двери — в соседний слева и соседний справа блок;
  • «|» означает, что этот блок имеет 2 двери — в соседний сверху и снизу блоки;
  • «^» означает, что этот блок имеет 1 дверь — в соседний сверху блок;
  • «>» означает, что этот блок имеет 1 дверь — в соседний справа блок;
  • «<» означает, что этот блок имеет 1 дверь — в соседний слева блок;
  • «v» означает, что этот блок имеет 1 дверь — в соседний снизу блок;
  • «L» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний слева блок;
  • «R» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний справа блок;
  • «U» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний сверху блок;
  • «D» означает, что этот блок имеет 3 двери — отсутствует дверь в соседний снизу блок;
  • «*» означает, что этот блок является стеной и не имеет дверей.

Лево, право, верх и низ определяются из представления лабиринта в виде таблицы, где строки пронумерованы сверху вниз от 1 до n, а столбцы слева направо от 1 до m.

В предпоследней строке содержатся два целых числа — координаты блока (xT, yT) (1 ≤ xT ≤ n, 1 ≤ yT ≤ m), где находится Тесей.

В последней строке содержатся два целых числа — координаты блока (xM, yM) (1 ≤ xM ≤ n, 1 ≤ yM ≤ m), где расположен Минотавр.

Гарантируется, что блок, в котором находится Минотавр (а также блок, в котором находится Тесей), не является блоком-стеной. Блоки, в которых изначально находятся Минотавр и Тесей, могут совпадать.

Выходные данные

Если Тесей не сможет добраться до Минотавра, то выведите -1 в единственной строке выходных данных. В противном случае выведите минимальное количество минут, за которое он сможет это сделать.

Примеры
Входные данные
2 2
+*
*U
1 1
2 2
Выходные данные
-1
Входные данные
2 3
<><
><>
1 1
2 1
Выходные данные
4
Примечание

В момент времени 0 Тесей уже находится в лабиринте в блоке с координатами (xT, yT).