SOLVE

LATER

Grid

/

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\)

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