떨어진 사과와 가장 가까운 나무

사과는 나무에서 멀리 떨어지지 않는다는 말이 있다. 정말 그럴까?

통계청은 어느 과수원에서 사과가 떨어진 자리를 $G$년 동안 해마다 기록했다. 과수원은 $R$개의 행과 $S$개의 열로 이루어진 격자이고, 한 칸에 사과나무가 두 그루 이상 있을 수도 있다.

해마다 사과는 정확히 한 번 떨어졌다. 그래서 통계청은 $i$번째 해에 사과가 떨어진 칸의 행 번호와 열 번호를 $(r_i, s_i)$로 적어 두었다. 사과가 떨어진 칸에는 다음 해까지 새 나무가 한 그루 자라났다.

해마다 사과가 떨어진 칸과 가장 가까운 나무 사이의 거리의 제곱을 구하라. 거리는 격자의 칸을 단위로 재고, 사과는 가장 가까운 그 나무에서 떨어졌다고 본다.

두 칸 $(r_1, s_1)$과 $(r_2, s_2)$ 사이의 거리는 다음과 같이 계산한다.

$d((r_1, s_1), (r_2, s_2)) = \sqrt{(r_1 - r_2)^2 + (s_1 - s_2)^2}$

첫째 줄에 격자의 행 개수 $R$과 열 개수 $S$가 주어진다. ($1 \le R, S \le 500$)

다음 $R$개의 줄에는 각각 문자 x 또는 .이 $S$개씩 주어진다. .은 빈 칸이고, x는 나무가 한 그루 이상 있는 칸이다.

처음 과수원에는 나무가 적어도 한 그루 있다.

그다음 줄에 관찰한 연수 $G$가 주어진다. ($1 \le G \le 10^5$)

다음 $G$개의 줄에는 각각 그해에 사과가 떨어진 칸의 행 번호와 열 번호를 뜻하는 두 정수 $r_i$, $s_i$가 주어진다. ($1 \le r_i \le R$, $1 \le s_i \le S$)

$G$개의 줄에 해마다 구한 거리의 제곱을 입력 순서대로 한 줄에 하나씩 출력한다.

사과가 이미 나무가 있는 칸에 떨어지면 거리의 제곱은 $0$이다.

어떤 해에 사과가 떨어져 자란 나무는 그다음 해부터 나무로 센다. 즉 그해의 답을 구할 때는 아직 세지 않는다.

가장 가까운 나무가 여러 그루여도 거리의 제곱은 하나로 정해진다.