Grid
/

Algorithms, Graph, Shortest path problem

Problem
Editorial
Analytics

You are given a grid A of size $N \times M$, two integers ($S_i, S_j$) and Q tasks. Each task contains two integers, ($D_{i},D_{j}$). Each cell in the grid is either empty cells denoted by O (Capital English character 'o') or occupied cells denoted by $*$. Initially, you are at ($S_{i},S_{j}$). Find the minimum number of steps in which you have to take to reach ($D_{i},D_{j}$) from ($S_{i},S_{j}$) without traversing the occupied cells.

In a single step, you can move from any cell (i,j) to the 4 neighboring cells i.e. ($i-1$,j), ($i+1$,j), (i,$j-1$) and (i,$j+1$) provided these cells are inside the grid A.

Input Foramt
The first line of input contains 3 space separated integers N, M and Q where N and M denotes the dimensions of the grid A and Q denotes the number of tasks.
Each of the next N lines contain a string of length M, $j_{th}$ character in the $i_{th}$ line of which is either O or $*$ denoting that the cell ($i,j$) is empty or occupied.
The next line contains 2 space separated integers $S_{i}$ and $S_{j}$ denoting the source cell of the grid.
This is followed by Q lines each containing 2 space separated integers $D_{i}$ and $D_{j}$.

Output Format
Print the answer to each query on a new line. If there is no path between ($S_{i},S_{j}$) and ($D_{i},D_{j}$) , print $-1$.

Constraints

• $1 \le N,M \le 10^{3}$
• $1 \le Q \le 10^{5}$
• $A_{i,j}$ is either O or $*$
• $1 \le S_{i},D_{i} \le N$
• $1 \le S_{j},D_{j} \le M$
SAMPLE INPUT
3 3 2
O*O
OOO
*OO
2 2
1 1
1 2
SAMPLE OUTPUT
2
-1

Explanation

The shortest path from (2,2) to (1,1) is (2,2)->(2,1)->(1,1) consisting of 2 steps, hence the answer is 2.
No path exists from cell (2,2) to (1,2), hence the answer is $-1$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB