Ruudukossa osa ruuduista on turvallisia mutta joissakin ruuduissa on hirviö. Et voi olla samassa ruudussa hirviön kanssa. Voit yhdellä hypyllä siirtyä turvallisesta ruudusta toiseen turvalliseen ruutuun, joka on samalla rivillä tai samassa sarakkeessa.

Tehtäväsi on käsitellä useita kyselyjä, joissa sinun tulee ilmoittaa pienin mahdollinen hyppyjen määrä kahden turvallisen ruudun välillä.

Syöte

Ensimmäinen rivi sisältää kolme kokonaislukua n, m ja q: ruudukon korkeus ja leveys sekä kyselyiden määrä. Rivit on numeroitu 1,2,\dots,n ja sarakkeet on numeroitu 1,2,\dots,m.

Seuraavat n riviä kuvaavat ruudukon. Jokaisella rivillä on m merkkiä: merkki . tarkoittaa turvallista ruutua ja merkki * tarkoittaa ruutua, jossa on hirviö.

Viimeiset q riviä sisältävät kukin neljä kokonaislukua y_1, x_1, y_2 ja x_2: lähtöruudun rivi ja sarake sekä kohderuudun rivi ja sarake. Lähtöruutu ja kohderuutu ovat aina turvallisia ruutuja.

Tuloste

Tulosta q riviä: jokaisen kyselyn vastauksena pienin määrä hyppyjä, jolla lähtöruudusta pääsee kohderuutuun. Jos reitti ei ole mahdollinen, tulosta -1.

Esimerkki

Syöte:

4 6 5
.*.***
*...**
*****.
*..*.*
1 1 1 3
2 2 2 2
1 1 4 5
4 5 2 4
3 6 2 2

Tuloste:

1
0
3
3
-1

Selitys:

• Ensimmäisessä kyselyssä sinun tulee liikkua ruudusta (1,1) ruutuun (1,3). Yksi hyppy riittää, koska voit hypätä kaksi ruutua oikealle.
• Toisessa kyselyssä sekä lähtöruutu että kohderuutu on (2,2), joten hyppyjä ei tarvita.
• Kolmannessa kyselyssä paras ratkaisu on hypätä kolmesti: ensin kaksi askelta oikealle, sitten kolme askelta alaspäin ja lopuksi kaksi askelta oikealle.
• Myös neljännessä kyselyssä pienin hyppyjen määrä on kolme. Yksi ratkaisu on hypätä ensin kolme askelta vasemmalle, sitten kaksi askelta ylöspäin ja lopuksi kaksi askelta oikealle.
• Viidennessä kyselyssä reitti ei ole mahdollinen, koska lähtöruudusta ei pysty hyppäämään mihinkään muuhun ruutuun.

Osatehtävä 1 (10 pistettä)

• 1\le n, m, q\le 10

Osatehtävä 2 (20 pistettä)

• 1\le n, m\le 250
• 1\le q\le 250

Osatehtävä 3 (15 pistettä)

• 1\le n, m\le 40
• 1\le q\le 2\cdot10^5

Osatehtävä 4 (15 pistettä)

• 1\le n, m\le 80
• 1\le q\le 2\cdot10^5

Osatehtävä 5 (40 pistettä)

• 1\le n, m\le 250
• 1\le q\le 2\cdot10^5