LTRAFFIC - love and traffic

Arjun is very smart, hence has Q valentines.

He lives in the state A which is a matrix of size N x M, where each cell (i, j) represents a city. He lives in the city (S1, S2). His Q valentines live in different cities. He is supposed to attend all his valentines but he can't do so due to constraints of time. So he decides to celebrate this festival of love with the valentine who lives closest to his city.

In a single step, he 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).

But some cities have serious traffic problem. It is impossible to penetrate the traffic in those cities. So Arjun will avoid passing through them while going to his destination. These cities have value *. All other cities have value 1.

He wants to find out the number of steps required to reach his closest valentine.

Since he is more of a philosopher, he struggles with the math. So it's your job now to help him find out.

Input

The first line of input contains 3 space separated integers N, M and Q where N and M denotes the dimensions of the matrix A, and Q denotes the number of valentines.

Each of the next N lines contain a string of length M, where each character is either 1 or * as described above.

The next line contains 2 space separated integers S1 and S2 denoting coordinates of city Arjun lives in.

then Q lines follow, each line containing 2 space separated integers Di and Dj denoting the coordinates of city of that particular valentine.

Output

Print a single integer Z denoting number of steps to reach nearest valentine. If there is no path possible between (S1, S2) and any of (Di, Dj), print -1.

Example

Input:
5 4 4
11*1
*11*
*111
1111
111*
2 3
5 1
3 4
2 4
5 1

Output:
2

Explanation

To reach the nearest city, he takes the following path: (2, 3) → (3, 3) → (3, 4).


Added by:aman
Date:2019-02-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-08-25 08:45:15 Simes
Matrix size is greater than 100, but not greater than 1000.
2019-08-25 03:47:24
Alas, no limits are given :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.