---
title: Острів
---

Вам дано таблицю $n\times n$, де кожна клітинка — це суша або вода.
Рядки та стовпці таблиці пронумеровані $1,2,\dots,n$. Ви можете рухатися по таблиці, роблячи кроки вліво, вправо, вгору або вниз.
Дві клітинки зв'язані, якщо між ними можна переміститися за один або більше кроків, залишаючись на клітинках одного типу.

Клітинки суші утворюють один зв'язаний острів, а клітинки води утворюють один зв'язаний океан. Перший та останній рядки та стовпці містять лише клітинки води.

Ваше завдання — відповісти на $q$ запитів: дано дві клітинки суші $(r_1,c_1)$ та $(r_2,c_2)$, яка мінімальна кількість кроків потрібна, щоб переміститися з першої клітинки до другої, залишаючись на суші?

# Вхідні дані

Перший рядок містить два цілих числа $n$ та $q$: розмір таблиці та кількість запитів.

Наступні $n$ рядків містять по $n$ символів, що описують таблицю. "`.`" — це клітинка води, а "`#`" — це клітинка суші.

Наступні $q$ рядків містять по чотири цілих числа $r_1$, $c_1$, $r_2$ та $c_2$: рядок і стовпець першої клітинки, а потім рядок і стовпець другої клітинки.

# Вихідні дані

Виведіть відповідь на кожен запит в окремому рядку.

# Обмеження

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ у всіх запитах

# Приклад

Вхідні дані:
```
8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2
```

Вихідні дані:
```
5
0
17
3
```

# Оцінювання

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Жоден рядок чи стовпець не містить клітинок води між клітинками суші | [score=2] |
| 3       | Жоден квадрат $2\times2$ не складається лише з клітинок суші | [score=3] |
| 4       | Жоден рядок не містить клітинок води між клітинками суші | [score=4] |
| 5       | Без додаткових обмежень | [score=5] |
