---
title: Sala
---

Jums ir dota $n\times n$ tabula, kur katrs lauciņš ir vai nu zeme, vai arī ūdens. Rindas un kolonnas ir numurētas $1,2,\dots,n$. Jūs varat tabulā kustēties ar soļiem uz augšu, uz apakšu, pa labi, pa kreisi. Divi lauciņi ir savienoti, ja ir iespējams aizstaigāt no viena uz otru ar kaut kādu soļu skaitu, paliekot uz viena un tā paša tipa lauciņa.

Zemes lauciņi veido vienu savienotu salu un ūdens lauciņi veido vienu savienotu okeānu. Pirmās un pēdējās rindas un kolonnas ir ūdens lauciņi.

Jūsu uzdevums ir atbildēt uz $q$ vaicājumiem: ir doti divi zemes lauciņi $(r_1,c_1)$ un $(r_2,c_2)$. Kāds ir mazākais soļu skaits, lai aizstaigātu no pirmā lauciņa uz otru, staigājot tikai pa zemes lauciņiem?

# Ievaddati

Pirmajā ievaddatu rindā ir divi veseli skaitļi $n$ un $q$: tabulas izmērs un vaicājumu skaits.

Nākamajās $n$ rindās katrā ir $n$ simboli, kas apraksta tabulu. "`.`" ir ūdens lauciņš, un "`#`" ir zemes lauciņš.

Nākamās $q$ rindas katra satur četrus veselus skaitļus $r_1$, $c_1$, $r_2$ un $c_2$: rindas un kolonnas indeksi pirmajam un otrajam lauciņam katrā vaicājumā.

# Izvaddati

Izvadiet atbildi katram vaicājumam savā rindā.

# Ierobežojumi

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ visos vaicājumos

# Piemērs

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

Izvaddati:
```
5
0
17
3
```

# Vērtēšana

| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Nav tādas rindas vai kolonnas, kurā būtu ūdens lauciņš starp zemes lauciņiem | [score=2] |
| 3       | Nav tāda $2\times2$ kvadrāta, kurā būtu tikai zemes lauciņi | [score=3] |
| 4       | Nav tādas rindas, kurā būtu ūdens lauciņš starp zemes lauciņiem | [score=4] |
| 5       | Bez papildu ierobežojumiem | [score=5] |
