Water Bottle

JOI's city, IOI, is known to be very hot all year round.

IOI is a rectangle divided into $H$ rows and $W$ columns of cells. Each cell is a building, a field, or a wall. There are $P$ building cells, numbered from 1 to $P$.

JOI can enter only building cells and field cells. From a cell, JOI can move directly only to an adjacent cell that shares a side, and JOI cannot leave the city during a move.

JOI often walks between buildings for various errands. Buildings are air-conditioned, but fields are hot and sunny. Each field cell passed costs 1 unit of water. Fields have no vending machines or water fountains, so people usually carry a water bottle. A bottle of size $x$ holds at most $x$ units of water. Building cells have taps, so a bottle can be refilled to full there.

Large bottles are hard to carry, so JOI wants to use the smallest bottle possible. Write a program that finds, for each query, the minimum bottle size needed to travel between two given buildings.

You are given the map of IOI and $Q$ queries. The $i$-th query asks: what is the minimum bottle size needed to travel between buildings $S_i$ and $T_i$?

The first line contains four integers $H$, $W$, $P$, and $Q$ separated by spaces. These mean that IOI has $H$ rows and $W$ columns, has $P$ building cells, and has $Q$ queries.

The next $H$ lines describe the map. The $r$-th of these lines contains a string of $W$ characters, each either . or #. The character in column $c$ is . for a building or field and # for a wall.

The next $P$ lines give the building positions. The $j$-th line contains two integers $A_j$ and $B_j$. Building $j$ is in column $A_j$ counting from the top, and row $B_j$ counting from the left. The corresponding cell on the map is guaranteed to be ..

The next $Q$ lines each contain two integers $S_i$ and $T_i$.

Print $Q$ lines. On line $i$, print the minimum bottle size needed to travel between buildings $S_i$ and $T_i$. If the trip is impossible, print -1. If the trip can be made without passing any field cell, print 0.

• $1 \le H \le 2000$
• $1 \le W \le 2000$
• $2 \le P \le 200000$
• $1 \le Q \le 200000$
• $1 \le A_j \le H$ for all $j$
• $1 \le B_j \le W$ for all $j$
• $(A_i, B_i) \ne (A_j, B_j)$ for $i < j$
• $1 \le S_i < T_i \le P$ for all $i$