시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB125562.500%

문제

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

Ловушка представляет из себя матрицу размера $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$, если это невозможно.

예제 입력 1

2 2
1 1
2 2
.4
2.

예제 출력 1

8

예제 입력 2

1 5
1 1
1 5
.007.

예제 출력 2

-1

예제 입력 3

3 3
1 1
3 3
.05
655
01.

예제 출력 3

-1

예제 입력 4

3 3
1 1
3 3
.12
345
67.

예제 출력 4

7