---
title: Insel
---

Du erhältst ein $n\times n$-Gitter, in dem jedes Feld entweder Land oder Wasser ist.
Die Zeilen und Spalten des Gitters sind mit $1, 2, \dots, n$ nummeriert. Du kannst dich im Gitter bewegen, indem du Schritte nach links, rechts, oben oder unten machst.
Zwei Felder sind zusammenhängend, wenn du dich zwischen ihnen bewegen kannst und sie von der gleichen Art sind.

Die Landfelder bilden eine zusammenhängende Insel, und die Wasserfelder bilden einen zusammenhängenden Ozean. Die erste und die letzte Zeile sowie die erste und die letzte Spalte enthalten ausschließlich Wasserfelder.

Deine Aufgabe ist es, $q$ Abfragen zu beantworten: Gegeben seien zwei Landfeldern $(r_1,c_1)$ und $(r_2,c_2)$, wie viele Schritte sind mindestens erforderlich, um vom ersten Feld zum zweiten zu gelangen, ohne das Land zu verlassen?

# Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $q$: die Größe des Gitters und die Anzahl der Abfragen.

Die nächsten $n$ Zeilen enthalten jeweils $n$ Zeichen, die das Gitter beschreiben. „`.`“ steht für ein Wasserfeld und „`#`“ für ein Landfeld.

Die nächsten $q$ Zeilen enthalten jeweils vier ganze Zahlen $r_1$, $c_1$, $r_2$ und $c_2$: die Zeile und Spalte des ersten Feldes, gefolgt von der Zeile und Spalte des zweiten Feldes.

# Ausgabe

Gib die Antwort auf jede Abfrage in separaten Zeilen aus.

# Beschränkungen

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ in allen Abfragen

# Beispiel

Eingabe:
```
8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2
```

Ausgabe:
```
5
0
17
3
```

# Bewertung

| Teilaufgabe | Beschränkungen | Punkte |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Keine Zeile und keine Spalte enthält Wasserfelder zwischen Landfeldern | [score=2] |
| 3       | Kein $2\times2$-Quadrat besteht ausschließlich aus Landfeldern | [score=3] |
| 4       | Keine Zeile enthält Wasserfelder zwischen Landfeldern | [score=4] |
| 5       | Keine weiteren Beschränkungen | [score=5] |
