---
title: Saari
---

Annettuna on $n\times n$-ruudukko, jossa jokainen ruutu on maata tai vettä.
Ruudukon rivit ja sarakkeet on numeroitu $1,2,\dots,n$. Voit liikkua ruudukossa kulkemalla askelia vasemmalle, oikealle, ylöspäin tai alaspäin. Kaksi ruutua ovat yhteydessä toisiinsa, jos voit kulkea niiden välillä saman tyyppisiä ruutuja käyttäen.

Kaikki maaruudut ovat yhteydessä toisiinsa ja muodostavat saaren. Vastaavasti kaikki vesiruudut ovat yhteydessä toisiinsa ja muodostavat meren. Ruudukon ensimmäinen ja viimeinen rivi ja sarake muodostuvat kokonaan vesiruuduista.

Tehtäväsi on vastata $q$ kyselyyn: annettuna on kaksi maaruutua $(r_1,c_1)$ ja $(r_2,c_2)$, mikä on pienin askelten määrä, kun liikutaan ensimmäisestä ruudusta toiseen ruutuun maalla pysyen?

# Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$: ruudukon koko ja kyselyiden määrä.

Seuraavilla $n$ rivillä on kullakin $n$ merkkiä, jotka kuvaavat ruudukon: "`.`" on vesiruutu ja "`#`" on maaruutu.

Seuraavilla $q$ rivillä on kullakin neljä kokonaislukua $r_1$, $c_1$, $r_2$ ja $c_2$: ensin ensimmäisen ruudun rivi ja sarake ja sitten toisen ruudun rivi ja sarake.

# Tuloste

Tulosta kunkin kyselyn vastaus omalle rivilleen.

# Rajat

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ kaikissa kyselyissä

# Esimerkki

Syöte:
```
8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2
```

Tuloste:
```
5
0
17
3
```

# Pisteytys

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Millään rivillä tai sarakkeella ei ole vesiruutuja maaruutujen välissä | [score=2] |
| 3       | Missään $2\times2$-neliössä ei ole pelkkiä maaruutuja | [score=3] |
| 4       | Millään rivillä ei ole vesiruutuja maaruutujen välissä | [score=4] |
| 5       | Ei lisärajoituksia | [score=5] |
