Ми маємо шахівницю \(N \times N\). Нехай (\(i, j\)) позначає квадрат у \(i\)-му рядку зверху та \(j\)-му стовпчику зліва цієї дошки. Дошка описується \(N\) рядками \(S_i\). \(j\)-й символ рядка \(S_i\), \(S_{i,j}\), означає наступне.

• Якщо \(S_{i,j}=\)'.', квадрат (\(i, j\)) порожній.

• Якщо \(S_{i,j}=\)'#', поле (\(i, j\)) зайнято білим пішаком, який не можна пересунути або видалити.

Ми поставили білого слона на поле (\(A_x, A_y\)).

Знайдіть мінімальну кількість ходів, необхідну для переміщення цього слона з (\(A_x, A_y\)) до (\(B_x, B_y\)) за правилами гри в шахи. Якщо його неможливо перемістити в (\(B_x, B_y\)), то виведіть -1.

Обмеження

• \(2 \le N \le 1500\)

• \(1 \le A_x,A_y \le N\)

• \(1 \le B_x,B_y \le N\)

• \((A_x,A_y) \neq (B_x,B_y)\)

• \(S_i\) це рядок довжини \(N\), що складається з '.' і '#'.

• \(S_{A_x,A_y}=\) '.'

• \(S_{B_x,B_y}=\) '.'

Формат вхідних даних

Перший рядок містить ціле число \(N\)

Наступний  рядок містить \(2\) цілих чисел \(A_x, A_y\)

Третій  рядок містить \(2\) цілих чисел \(B_x, B_y\)

Наступні  \(N\) рядків містять \(S_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

Ми можемо перемістити слона з (1,3) до (3,5) за три ходи, як зазначено нижче, але не за два чи менше ходів.

• (1,3)→(2,2)→(4,4)→(3,5)

Приклад вхідних даних

5
1 3
3 5
....#
...#.
.....
.#...
#....

Приклад вихідних даних

3

Приклад вхідних даних

4
3 2
4 2
....
....
....
....

Приклад вихідних даних

-1

Приклад вхідних даних