SOLVE
LATER
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
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\).