Стрелочник

Загулявшись поздно Хэллоуинской ночью, вы и сами не заметили, как попали в ловушку к демону-стрелочнику. Было бы здорово выбраться из нее до рассвета, а иначе у вас будут все шансы остаться в ней навсегда (ну или как минимум до следующего Хэллоуина).

Ловушка представляет из себя матрицу размера $n \times m$. Некоторые клетки матрицы пусты, а в некоторых нарисованы стрелочки в соседние по стороне или углу клетки. Каждую секунду все стрелочки поворачиваются на $45^\circ$ градусов по часовой стрелке.

Обозначим направление вверх как $0$, вправо-вверх как $1$ и так далее, пустую клетку обозначим точкой. Вы находитесь в клетке с координатами $(a\_x, a\_y)$, и,

• находясь в пустой клетке, можете либо секунду подождать в ней, либо за секунду переместиться в соседнюю по стороне клетку;
• попадая на клетку со стрелочкой, вы моментально (за $0$ секунд) переноситесь туда, куда она указывает.

Когда вы переходите на клетку со стрелкой, она уже успевает повернуться за ту секунду, что вы шагали. Ваша задача --- выбраться из ловушки как можно скорее. Попадите из стартовой точки $(a\_x, a\_y)$ в конечную $(b\_x, b\_y)$ за минимальное количество секунд, либо определите, что это невозможно, и смиритесь с тем, что вам не выбраться.

В первой строке через пробел даны два целых числа $n$ и $m$ --- размеры ловушки ($1 \leqslant n, m \leqslant 1000$).

Во второй строке даны два целых числа $a\_x$ и $a\_y$ --- координаты стартовой клетки ($1 \leqslant a\_x \leqslant n$; $1 \leqslant a\_y \leqslant m$).

В третьей строке так же даны два целых числа $b\_x$ и $b\_y$ --- координаты конечной клетки ($1 \leqslant b\_x \leqslant n$, $1 \leqslant b\_y \leqslant m$).

Далее следуют $n$ строк по $m$ символов --- описание матрицы. Гарантируется, что ни в стартовой, ни в конечной точке нет стрелочек.

В качестве ответа выведите минимальное время, необходимое, чтобы добраться из $(a\_x, a\_y)$ в $(b\_x, b\_y)$, либо $-1$, если это невозможно.