The city of IOI, where JOI-kun lives, is known to be very hot throughout the year. The city of IOI is a rectangle divided into a grid of $H \times W$ cells. Each cell is either a building, a field, or a wall. There are $P$ building cells, numbered from 1 to $P$.

JOI-kun can only enter building or field cells. He can only move directly between adjacent cells (i.e., cells that share a side), and he cannot leave the city of IOI during his movement.

JOI-kun needs to walk between various buildings for his errands. While the interiors of buildings are air-conditioned, fields are hot due to strong sunlight, and he requires 1 unit of water for every field cell he passes through. Furthermore, since there are no vending machines or water fountains in the fields, it is common in the city of IOI to carry a water bottle. A water bottle of size $x$ can hold up to $x$ units of water. Since there is a water supply in every building cell, he can refill his water bottle to its full capacity at any building.

Because large water bottles are difficult to carry, JOI-kun wants to use the smallest possible water bottle for his travels. Write a program that, for several movements between buildings, determines the minimum size of the water bottle required for that movement.

Input

Read the following data from standard input:

• The first line contains four space-separated integers $H, W, P, Q$. This indicates that the city of IOI is a rectangle of $H \times W$ cells, there are $P$ building cells in the city, and there are $Q$ questions to be answered.
• The next $H$ lines contain the map of the city of IOI. The $r$-th line ($1 \le r \le H$) contains a string of $W$ characters, where each character is either "." or "#". The $c$-th character of this string ($1 \le c \le W$) represents the cell at the $r$-th row from the top and $c$-th column from the left, where "." represents a building or a field, and "#" represents a wall.
• The next $P$ lines contain the locations of the buildings in the city of IOI. The $j$-th line ($1 \le j \le P$) contains two space-separated integers $A_j, B_j$. This indicates that building $j$ is located at the $A_j$-th row from the top and $B_j$-th column from the left. It is guaranteed that the corresponding cell on the map provided earlier is ".".
• The next $Q$ lines contain the questions. The $i$-th line ($1 \le i \le Q$) contains two space-separated integers $S_i, T_i$. This indicates that the $i$-th question is "What is the minimum size of the water bottle required to travel between building $S_i$ and building $T_i$?".

Output

Output $Q$ lines to standard output. The $i$-th line ($1 \le i \le Q$) should contain an integer representing the minimum size of the water bottle required to travel between building $S_i$ and building $T_i$. If the movement is impossible, output -1. If the movement can be made without passing through any field cells, output 0.

Constraints

All input data satisfies the following conditions:

• $1 \le H \le 2000$.
• $1 \le W \le 2000$.
• $2 \le P \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $1 \le A_j \le H$ ($1 \le j \le P$).
• $1 \le B_j \le W$ ($1 \le j \le P$).
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \le i < j \le P$).
• $1 \le S_i < T_i \le P$ ($1 \le i \le Q$).

Subtasks

Subtask 1 [10 points]

• $H \le 200$.
• $W \le 200$.
• $P \le 200$.

Subtask 2 [30 points]

• $P \le 5000$.
• $Q = 1$.

Subtask 3 [30 points]

• $P \le 5000$.
• $Q \le 10\,000$.

Subtask 4 [30 points]

• No additional constraints.

Examples

Input 1

5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4

Output 1

3
4
4
2

Input 2

5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3

Output 2

-1
7