전력 수요

당신은 도시에 새 공장을 지으려고 한다. 이 공장은 전력 수요가 크기 때문에 발전소와 가까운 곳에 두는 것이 중요하다. 그래서 가능한 후보 위치들을 우선순위 순으로 정렬한 목록을 만들려고 한다.

공장을 세울 수 있는 영역은 $N$개의 행과 $M$개의 열로 이루어진 직사각형 격자이다. 일부 칸에는 발전소가 있다. 공장은 정확히 한 칸을 차지하며, 발전소가 없는 빈 칸이면 어디에나 놓을 수 있다.

행은 위에서부터 $1$부터 $N$까지, 열은 왼쪽에서부터 $1$부터 $M$까지 번호를 매긴다. 칸 $(i, j)$는 $i$번째 행, $j$번째 열의 칸을 뜻한다. 두 칸 $(i_0, j_0)$과 $(i_1, j_1)$ 사이의 거리는 $\max(|i_0 - i_1|, |j_0 - j_1|)$로 정의하며, 여기서 $|x|$는 $x$의 절댓값이다. 한 위치의 전력 우선도는 그 칸에서 가장 가까운 발전소까지의 거리이다.

이제 모든 빈 칸에 $1$부터 시작하는 연속한 정수를 매긴다. 먼저 전력 우선도가 작은 순서로 매기고, 전력 우선도가 같으면 행 번호가 작은 순서로, 행 번호까지 같으면 열 번호가 작은 순서로 매긴다.

예를 들어 $4 \times 7$ 격자에서, 발전소로부터의 거리가 $1$인 빈 칸들은 모두 전력 우선도 $1$을 받고, 그 바깥쪽 칸들은 우선도 $2$를 받는 식이다. 그렇게 우선도를 정한 뒤 위 규칙에 따라 빈 칸에 번호를 매긴다.

이렇게 만든 목록에 대해 여러 개의 질의가 주어진다. 각 질의는 목록에서의 위치(순번)를 주며, 그 순번을 배정받은 칸이 어디인지 답해야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $N$, $M$, $P$가 주어진다. 각각 격자의 행 수, 열 수($1 \le N, M \le 10^9$), 발전소의 개수($1 \le P \le 20$)이다. 이어지는 $P$개의 줄에는 각각 두 정수 $R$과 $C$가 주어지며, 이는 한 발전소의 행과 열을 나타낸다($1 \le R \le N$, $1 \le C \le M$). 한 테스트 케이스 안에서 모든 발전소의 위치는 서로 다르다. 다음 줄에는 질의의 개수 $Q$가 주어진다($1 \le Q \le 50$). 그다음 줄에는 $Q$개의 정수 $p_1, \dots, p_Q$가 주어지며, 각각 목록에서의 위치이다($1 \le p_i \le N \times M - P$).

마지막 테스트 케이스 뒤에는 세 개의 $0$으로 이루어진 줄(0 0 0)이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $Q + 1$개의 줄을 출력한다. $i = 1, \dots, Q$에 대해 $i$번째 줄에는 위치 $p_i$를 배정받은 칸의 행과 열, 두 정수를 출력한다. 이 $Q$개의 줄 다음에는 하이픈 문자 - 하나만 있는 줄을 출력한다.