청소기 로봇

가구가 배치된 방에 청소기 로봇이 있다. 방은 세로 $N$칸, 가로 $M$칸인 $2$차원 격자칸으로 표현한다. 각 칸은 로봇이 갈 수 있는 칸과 가구가 배치되어 갈 수 없는 칸들로 구별된다고 한다. 격자의 가장 바깥쪽 한 줄은 모두 갈 수 없는 칸들이라고 가정한다. 또, 갈 수 없는 칸들이 상하좌우로 인접한 것은 연결된 것이라고 했을 때, 모든 갈 수 없는 칸들은 연결되어 있다.

$Q$개의 쿼리가 주어진다. 각 쿼리는 격자칸의 위치 두 개이다. 각 위치는 $(\textrm{행번호}, \textrm{열번호})$의 좌표로 주어진다. 행 번호는 위에서부터 $1$로 시작하여 $N$까지, 열 번호는 왼쪽에서부터 $1$로 시작하여 $M$까지 번호가 매겨진다. 각 쿼리에 대한 대답은 주어진 위치들을 연결하는 가장 짧은 길의 길이이다. 로봇은 상하좌우로 인접한 칸으로만 움직일 수 있다. 길의 길이는 로봇이 인접한 칸으로 이동한 횟수로 표현한다.

주어진 가구 배치에 대해서 쿼리들에 대한 대답을 계산하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 그려지는 세로 칸 수 $N$, 가로 칸 수 $M$, 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($3 \le N, M \le 1\,000$, $1 \le Q \le 200\,000$)

다음 $N$개의 줄에는 방의 배치를 나타내는 $M$개의 글자가 각각 주어진다. 각 글자는 .인 경우 로봇이 갈 수 있는 칸, #인 경우 로봇이 갈 수 없는 칸이다.

다음 $Q$개의 줄에 쿼리가 하나씩 주어진다. 각 쿼리는 $R_1$, $C_1$, $R_2$, $C_2$ 네 개의 정수가 공백으로 구분되어 주어진다. 이는 쿼리의 두 위치의 좌표가 $(R_1, C_1)$와 $(R_2, C_2)$임을 의미한다. 또한 좌표는 로봇이 갈 수 있는 칸들에 대해서만 주어진다.

출력 형식

각 쿼리에 대해서 한 줄에 정수를 하나 출력한다. 두 위치 간을 이동하는 것이 가능한 경우 가장 짧은 길의 길이를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

예제

6 6 2
######
#....#
#.##.#
#.#.##
#.#.##
######
5 2 3 5
5 2 5 4

7
-1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

###########
####..#####
##.......##
###.....###
#####.....#
#####.#####
#.....#####
#####.....#
#####.#####
##.....####
###......##
###########

해설