물병 Batch 컴파일 명령

승현이가 사는 IOI 시는 일년 내내 매우 덥습니다.

IOI 시는 $H \times W$ 크기의 직사각형 격자판 형태입니다. 각 격자는 크기가 모두 같은 정사각형 모양이며 건물, 들판, 벽 중 하나입니다. 건물이 있는 격자는 총 $P$개 있으며, 각 격자에는 $1$ 이상 $P$ 이하의 자연수 번호가 매겨져 있습니다.

승현이는 건물 또는 들판이 있는 격자에만 들어갈 수 있습니다. 또한 임의의 격자에서 이동 가능한 격자는 변 하나를 공유하는 네 개의 격자들뿐이며, 승현이는 이동 중 IOI 시를 빠져나갈 수는 없습니다.

승현이는 각종 심부름을 하기 위해 다양한 건물들을 돌아다녀야 합니다. 건물 안은 냉방이 되기 때문에 시원하지만, 들판은 강한 햇빛 때문에 매우 덥기 때문에, 승현이는 들판이 있는 격자를 한 칸 지날 때마다 물 1리터를 마셔야 합니다. 또한 들판의 온도는 너무 높아 음료수 자판기나 식수대를 둘 수는 없기 때문에, 승현이는 물병을 가지고 돌아다닙니다. 크기가 $x$인 물통에는 물을 최대 $x$ 리터까지 넣을 수 있습니다. 모든 건물 격자에는 식수대가 있으므로 식수로 물통을 가득 채울 수 있습니다.

그러나 큰 물통을 들고 다니는 것은 고역이므로, 승현이는 가능한 한 작은 물병을 가지고 돌아다니고 싶습니다. 그래서 어떤 두 건물 사이를 돌아다닐 때 승현이가 들고 다녀야 할 물통의 크기의 최솟값을 구하는 프로그램을 작성하고자 합니다.

해야 할 일

IOI 시의 지도와 $Q$개의 질의가 주어집니다. 이 중 $i$번째 ($1 \le i \le Q$) 질의는 "$S_{i}$번 건물과 $T_{i}$번 건물 사이를 이동하는 데 필요한 물통 크기의 최솟값은 얼마인가?"라는 것입니다. 이 때 각 질의에 답하는 프로그램을 작성하세요.

입력 형식

표준 입력으로 아래 입력을 받습니다.

• 첫 번째 줄에 네 개의 정수 $H, W, P, Q$가 공백을 사이로 두고 주어집니다. 이것은 IOI 시는 $H$행 $W$열의 격자판 모양이며, 건물 격자는 $P$개 있고, 질의의 수는 $Q$개임을 나타냅니다.
• 다음 $H$개 줄에 IOI 시의 지도가 주어집니다. 이 중 $r$번째 줄 ($1 \le r \le H$)에는 길이가 $W$인 문자열이 주어지며, 이 문자열은 '.' 또는 '#'로만 구성되어 있습니다. 이 문자열의 $c$번째 문자 ($1 \le c \le W$)는 IOI 시에서 $r$행 $c$열에 위치한 격자의 종류를 나타내는데, 문자가 .라면 해당 격자는 들판 또는 건물이라는 것이고, 문자가 #이라면 해당 격자는 벽이라는 것입니다.
• 다음 $P$개 줄에는 IOI 시에 위치한 건물들의 위치가 주어집니다. 이 중 $j$번째 줄 ($1 \le j \le P$)에는 두 개의 정수 $A_{j}$와 $B_{j}$가 공백을 사이로 두고 주어집니다. 이것은 $j$번 건물이 IOI 시의 $A_{j}$행 $B_{j}$열에 위치한 격자에 있다는 것을 나타냅니다. 위에서 주어진 지도에서 해당 칸은 .임이 보장됩니다.
• 다음 $Q$개 줄에는 질의들이 주어집니다. 이 중 $i$번째 줄 ($1 \le i \le Q$)에는 두 개의 정수 $S_{i}$와 $T_{i}$가 공백을 사이로 두고 주어집니다. 이것은 $i$번째 질의가 "$S_{i}$번 건물과 $T_{i}$번 건물 사이를 이동하는 데 필요한 물통 크기의 최솟값은 얼마인가?"라는 것을 나타냅니다.

출력 형식

표준 출력에 $Q$개 줄을 출력합니다. 이 중 $i$번째 줄 ($1 \le i \le Q$)에는 $S_{i}$번 건물과 $T_{i}$번 건물 사이를 이동하는 데 필요한 물통 크기의 최솟값을 출력합니다. 그러나 이동이 불가능한 경우 $-1$을 출력해야 합니다. 또한 들판 격자를 방문하지 않고 이동 가능할 경우 $0$을 출력합니다.

제약 조건

입력 데이터들은 아래 조건을 만족합니다.

• $1 \le H \le 2,000$
• $1 \le W \le 2,000$
• $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$)

서브태스크

서브태스크 1 [10점]

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

서브태스크 2 [30점]

• $P \le 5,000$
• $Q = 1$

서브태스크 3 [30점]

• $P \le 5,000$
• $Q \le 10,000$

서브태스크 4 [30점]

추가 제약 조건이 없습니다.

예제

이 입력에서 IOI 시의 지도는 아래와 같습니다. 검은 사각형이 들어 있는 격자는 벽 격자를, 숫자가 적혀 있는 격자는 해당 번호의 건물이 들어 있는 격자를, 아무것도 들어 있지 않는 격자는 들판 격자를 나타냅니다.

예로 들어 2번 건물에서 4번 건물로 이동한다고 생각해 봅시다.

이 때 다른 건물을 거치지 않는 경우 왼쪽 그림에서 점으로 표시된 경로를 통해 이동하면 되기 때문에 크기가 6인 물병이 필요합니다.

그러나 오른쪽 그림과 같이 1번 건물을 방문하게 된다면, 2번 건물과 1번 건물 사이에 들판 격자 3칸, 1번 건물과 4번 건물 사이에 들판 격자 4칸을 이동하면 되므로 크기가 4인 물병만 가지고 이동할 수 있습니다. 이보다 더 작은 물통으로 이동할 수 없습니다.

위 입력에서 1번 건물과 2번 건물 사이에 벽이 있으므로 이 두 건물 사이는 이동할 수 없습니다.