---
title: Eyja
---

Þér er gefin $n\times n$ grind þar sem hver reitur í grindinni er annaðhvort land eða vatn.
Raðirnar og dálkarnir í grindinni eru númeraðir $1,2,\dots,n$. Þú mátt hreyfa þig í grindinni með því að taka skref til vinstri, hægri, upp eða niður.
Tveir reitir eru tengdir ef þú getur hreyft þig milli þeirra í einu eða fleiri skrefum og reitirnir eru af sömu tegund.

Land reitirnir mynda eina tengda eyju og allir vatns reitirnir mynda einn tengdan sjó. Fyrsta og seinasta röðin ásamt fyrsta og seinasta dálkinum innihalda aðeins vatns reiti.

Verkefnið þitt er að svara $q$ spurningum: gefið eru tveir land reitir $(r_1,c_1)$ og $(r_2,c_2)$, hver er minnsti fjöldi skrefa til að ferðast frá fyrsta reitnum til seinni reitsins með því að ferðast aðeins yfir land reiti.

# Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $q$: stærðin á grindinni og fjöldi spurninga.

Næstu $n$ línurnar eru með $n$ stafi sem lýsa grindinni. "`.`" er vatns reitur og "`#`" er land reitur.

Næstu $q$ línurnar eru með fjórar heiltölur $r_1$, $c_1$, $r_2$ and $c_2$: röð og dálkur fyrsta reitsins og svo röð og dálkur seinna reitsins.

# Úttak

Prentaðu svarið fyrir hverja spurningu, hvert svar á sér línu.

# Takmarkanir

- $3\le n\le 1000$
- $1\le q\le 10^5$
- $1 < r_1,c_1,r_2,c_2 < n$ fyrir hverja spurningu.

# Dæmi

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

Úttak:
```
5
0
17
3
```

# Stigagjöf

| Hópur   | Takmarkanir | Stig      |
| :-----: | ----------- | :-------: |
| 1       | $n \le 200$, $q \le 200$ | [score=1] |
| 2       | Engar raðir né dálkar eru með vatns reiti milli land reiti | [score=2] |
| 3       | Engir $2\times2$-kassar eru aðeins með land reiti | [score=3] |
| 4       | Engar raðir eru með vatns reiti milli land reiti | [score=4] |
| 5       | Engar frekar takmarkanir | [score=5] |
