---
title: Sala
---

Duota $n\times n$ lentelė, kurios kiekviena pozicija yra žemė arba vanduo.
Lentelės eilutės ir stulpeliai yra sunumeruoti $1,2,\dots,n$. Lentelėje galima judėti einant kairėn, dešinėn, aukštyn arba žemyn.
Du laukeliai yra laikomi sujungti, jei tarp jų galima nukeliauti judant tik per tokio paties tipo laukelius.

Visi žemės laukeliai sudaro vieną jungią salą, o visi vandens laukeliai - vieną jungų vandenyną. Pirmame ir paskutiniame stulpeliuose bei eilutėse yra tik vandens laukeliai.

Jums reikia atsakyti į $q$ užklausų: duotos žemės laukelių pozicijos $(r_1,c_1)$ ir $(r_2,c_2)$. Kiek mažiausiai žingsnių reikia norint žeme pereiti iš pirmojo langelio į antrąjį?

# Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $n$ ir $q$ – lentelės dydis ir užklausų skaičius.

Kitose $n$ eilučių yra po $n$ ženklų apibūdinančių lentelę. "`.`" yra vanduo, o "`#`" – žemė.

Tolimesnėse $q$ eilučių duota po keturis sveikuosius skaičius $r_1$, $c_1$, $r_2$ ir $c_2$ – pirmojo langelio eilutė ir stulpelis bei antrojo langelio eilutė ir stulpelis.

# Išvestis

Atsakymus į užklausas išveskite atskirose eilutėse.

# Ribojimai

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ visoms užklausoms

# Pavyzdys

Pradiniai duomenys:
```
8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2
```

Išvestis:
```
5
0
17
3
```

# Vertinimas

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Nė vienoje eilutėje ar stulpelyje nebus vandens tarp žemės laukelių | [score=2] |
| 3       | Joks $2\times2$ kvadratas nebus sudarytas vien iš žemės laukelių | [score=3] |
| 4       | Nė vienoje eilutėje nebus vandens tarp žemės laukelių | [score=4] |
| 5       | Papildomų ribojimų nėra | [score=5] |
