Closest DashMart

Grid characters: a space is a road, X is a wall, and D is a warehouse. You may only move up, down, left, or right; each query asks for the shortest distance to the nearest warehouse. A query on a wall cell, out of bounds, or with no reachable warehouse returns -1.

输入格式

R C Q, R lines of the character grid, and Q 0-based coordinates. Site supplement: R,C≤1000, RC≤200000, Q≤200000.

输出格式

Output Q distances.

样例 1

输入：

3 3 5
D  
 XX
   
0 0
0 2
2 0
1 1
9 0

输出：

0 2 2 -1 -1

样例 2

输入：

1 3 3
XDX
0 0
0 1
0 2

输出：

-1 0 -1

样例 3

输入：

2 1 2
D
X
0 0
1 0

输出：

0 -1