---
title: Saar
---

Sulle on antud $n\times n$ ruudustik, kus iga ruut on kas maa või vesi.
Ruudustiku read ja veerud on nummerdatud $1,2,\dots,n$. Sa saad ruudustikus liikuda, tehes samme vasakule, paremale, üles ja alla. 
Kaks ruutu on ühendatud, kui nende vahel saab liikuda ühe või mitme sammuga, liikudes mööda sama tüüpi ruute.

Maaruudud moodustavad ühe ühendatud saare ja veeruudud moodustavad ühe ühendatud ookeani. Esimestel ja viimastel ridadel ja veergudel on ainult veeruudud.

Sinu ülesandeks on vastata $q$ päringule: antud on kaks maaruutu $(r_1,c_1)$ ja $(r_2,c_2)$. Mis on minimaalne arv samme, mis on vaja esimeselt ruudult teisele liikumiseks, kasutades ainult maaruute?

# Sisend

Esimesel real on kaks täisarvu $n$ ja $q$: ruudustiku suurus ja päringute arv.

Järgmisel $n$ real on igaühel $n$ tähemärki, mis kirjeldavad ruudustikku. "`.`" on veeruut ja "`#`" on maaruut.

Järgmisel $q$ real on igaühel neli täisarvu $r_1$, $c_1$, $r_2$ ja $c_2$: esimese ruudu reanumber ja veerunumber ning teise ruudu reanumber ja veerunumber.

# Väljund

Väljasta iga päringu vastus eraldi real.

# Piirangud

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ iga päringu korral

# Näide

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

Väljund:
```
5
0
17
3
```

# Hindamine

| Grupp | Piirangud | Punktid    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Üheski reas ega veerus pole vett maaruutude vahel | [score=2] |
| 3       | Ei leidu $2\times2$-ruutu, kus on ainult maaruudud | [score=3] |
| 4       | Üheski reas pole vett maaruutude vahel | [score=4] |
| 5       | Lisapiirangud puuduvad | [score=5] |
