---
title: Wyspa
---

Dana jest plansza o rozmiarze $n \times n$, na której każda pole jest lądem lub wodą.
Wiersze i kolumny planszy są ponumerowane $1, 2, \dots, n$. Po planszy można się poruszać, wykonując kroki w lewo, w prawo, w górę lub w dół.
Dwa pola są połączone, jeśli można przemieścić się między nimi w jednym lub większej liczbie kroków, pozostając na tym samym typie terenu.

Pola lądu tworzą jedną spójną wyspę, a pola wody tworzą jeden spójny ocean. Pierwszy i ostatni wiersz oraz pierwsza i ostatnia kolumna zawierają wyłącznie pola wody.

Twoim zadaniem jest odpowiedzieć na $q$ zapytań: dla dwóch danych pól lądu $(r_1, c_1)$ i $(r_2, c_2)$, jaka jest minimalna liczba kroków potrzebna do przemieszczenia się z pierwszego pola do drugiego, pozostając cały czas na lądzie?

# Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $q$: rozmiar planszy oraz liczbę zapytań.

Kolejne $n$ wierszy zawiera po $n$ znaków opisujących planszę. „`.`” oznacza pole wody, a „`#`” oznacza pole lądu.

Następne $q$ wierszy zawiera po cztery liczby całkowite $r_1, c_1, r_2, c_2$: wiersz i kolumnę pierwszego pola oraz wiersz i kolumnę drugiego pola.

# Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

# Ograniczenia

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ dla wszystkich zapytań

# Przykład

Wejście:
```
8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2
```

Wyjście:
```
5
0
17
3
```

# Ocenianie

| Podzadanie | Ograniczenia | Punkty    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | W żadnym wierszu ani kolumnie nie ma pól wody między polami lądu | [score=2] |
| 3       | Żaden kwadrat $2\times2$ nie składa się wyłącznie z pól lądu | [score=3] |
| 4       | W żadnym wierszu nie ma pól wody między polami lądu | [score=4] |
| 5       | Brak dodatkowych ograniczeń | [score=5] |
