시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB72447.018%

문제

Kasandra je napokon otvorila svoju prvu turističku agenciju. Njezina putovanja zasad su ograničena na Hrvatsku, koju možemo zamisliti kao tablicu dimenzija $N \times M$. 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$.

입력

U prvom su retku prirodni brojevi $N$ ($1 ≤ N ≤ 300$), $M$ ($1 ≤ M ≤ 300$) i $Q$ ($1 ≤ Q ≤ 100\,000$) 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 $A_i$, $B_i$, $C_i$, $D_i$ ($1 ≤ A_i, C_i ≤ N$) te ($1 ≤ B_i, D_i ≤ M$) gdje par brojeva $(A_i, B_i)$ označava redak i stupac početne točke te $(C_i, D_i)$ označava redak i stupac završnog odredišta.

출력

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

예제 입력 1

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

예제 출력 1

0
2
3
1

예제 입력 2

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

예제 출력 2

-1
3
-1