물통

JOI 군이 사는 IOI 시는 1년 내내 매우 더운 도시로 알려져 있다.

IOI 시는 세로 $H$칸, 가로 $W$칸으로 나뉜 직사각형이다. 각 칸은 건물, 들판, 벽 중 하나이다. 건물 칸은 $P$개이며 1번부터 $P$번까지 번호가 붙어 있다.

JOI 군은 건물 칸과 들판 칸에만 들어갈 수 있다. 한 칸에서 바로 이동할 수 있는 곳은 변을 공유하는 인접한 칸뿐이며, 이동 중에 IOI 시 밖으로 나갈 수는 없다.

JOI 군은 여러 용무 때문에 건물 사이를 걸어서 오가야 한다. 건물 안은 냉방이 되어 있지만 들판은 햇볕이 강해 덥다. 들판 칸을 하나 지날 때마다 물 1이 필요하다. 들판에는 자동판매기나 식수대가 없으므로 사람들은 보통 물통을 들고 이동한다. 크기가 $x$인 물통에는 물을 최대 $x$만큼 담을 수 있다. 건물 칸에는 수도가 있어서 물통을 가득 채울 수 있다.

큰 물통은 들고 다니기 불편하므로, JOI 군은 가능한 한 작은 물통으로 이동하려고 한다. 두 건물 사이를 이동하는 데 필요한 물통 크기의 최솟값을 질문마다 구하는 프로그램을 작성하라.

IOI 시의 지도와 $Q$개의 질문이 주어진다. $i$번째 질문은 건물 $S_i$와 $T_i$ 사이를 이동하는 데 필요한 물통 크기의 최솟값은 얼마인가이다.

첫 줄에는 공백으로 구분된 정수 $H$, $W$, $P$, $Q$가 주어진다. IOI 시는 세로 $H$칸, 가로 $W$칸이고, 건물 칸이 $P$개, 질문이 $Q$개라는 뜻이다.

이어서 $H$줄에 지도가 주어진다. $r$번째 줄은 $W$글자로 이루어진 문자열이며, 각 글자는 . 또는 #이다. $c$번째 글자가 .이면 건물 또는 들판, #이면 벽이다.

이어서 $P$줄에 건물의 위치가 주어진다. $j$번째 줄에는 정수 $A_j$, $B_j$가 주어지며, 건물 $j$가 위에서 $A_j$번째 열, 왼쪽에서 $B_j$번째 행에 있다는 뜻이다. 해당 칸은 반드시 .이다.

이어서 $Q$줄에 각각 정수 $S_i$, $T_i$가 공백으로 구분되어 주어진다.

$Q$줄을 출력한다. $i$번째 줄에는 건물 $S_i$와 $T_i$ 사이를 이동하는 데 필요한 물통 크기의 최솟값을 출력한다. 이동이 불가능하면 -1을 출력한다. 들판을 지나지 않고 이동할 수 있으면 0을 출력한다.

• $1 \le H \le 2000$
• $1 \le W \le 2000$
• $2 \le P \le 200000$
• $1 \le Q \le 200000$
• 모든 $j$에 대해 $1 \le A_j \le H$
• 모든 $j$에 대해 $1 \le B_j \le W$
• $i < j$이면 $(A_i, B_i) \ne (A_j, B_j)$
• 모든 $i$에 대해 $1 \le S_i < T_i \le P$