JHIO 2022. 2. zadatak

Kasandra je napokon otvorila svoju prvu turističku agenciju. Njezina putovanja zasad su ograničena na Hrvatsku, koju možemo zamisliti kao tablicu dimenzija NxM. Neka polja su lijepa i označena su znakovima “.”, dok su druga ružna i označena znakovima “#”. Turisti se mogu kretati samo u četiri osnovna smjera: gore, dolje, lijevo i desno.

Kasandra trenutno ima isplaniranih Q izleta, i za svaki od njih ju zanima minimalan potreban broj koraka od početne točke do završnog odredišta, ne prolazeći pritom ni jednim ružnim poljem. U slučaju da je nemoguće doći od početne točke do odredišta, ispišite -1.

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 300), M (1 ≤ M ≤ 300) i Q (1 ≤ Q ≤ 100000) iz teksta zadatka.

U sljedećih N redaka nalazi se tablica opisana na način iz teksta zadatka.

U sljedećih Q redaka nalaze se četvorke brojeva Ai, Bi, Ci, Di (1 ≤ Ai, Ci ≤ N) te (1 ≤ Bi, Di ≤ M) gdje par brojeva (Ai, Bi) označava redak i stupac početne točke te (Ci, Di) označava redak i stupac završnog odredišta.

Izlazni podaci

Potrebno je ispisati Q redaka, u i-ti udaljenost početne točke i odredišta i-tog izleta.

Probni primjeri

Ulaz

5 6 4
#...#.
......
#.#.#.
....#.
......
4 1 4 1
2 4 1 3
5 1 3 2
5 1 4 1

Izlaz

0
2
3
1

Ulaz

4 4 3
....
....
##..
.#..
4 1 3 3
2 3 1 1
1 4 4 1

Izlaz

-1
3
-1