Excursions

Kasandra finally opened her first travel agency. Her trips are limited to Croatia for now, which we can picture as a table of size $N \times M$. Some cells are nice and marked with ., while the others are ugly and marked with #. Tourists can move in only four basic directions: up, down, left, and right.

Kasandra currently has $Q$ planned trips. For each one, she wants the minimum number of steps from the starting point to the final destination without passing through any ugly cell. If the destination cannot be reached from the starting point, print $-1$.

The first line contains the natural numbers $N$ ($1 \le N \le 300$), $M$ ($1 \le M \le 300$), and $Q$ ($1 \le Q \le 100\,000$).

The next $N$ lines describe the table as explained in the problem.

The next $Q$ lines each contain four numbers $A_i$, $B_i$, $C_i$, $D_i$ ($1 \le A_i, C_i \le N$, $1 \le B_i, D_i \le M$). The pair $(A_i, B_i)$ is the row and column of the starting point, and $(C_i, D_i)$ is the row and column of the destination.

Print $Q$ lines. The $i$-th line contains the distance between the starting point and the destination of the $i$-th trip.