북극곰

직사각형 격자가 아니라 극좌표 모눈종이 위에서 진행하는 콘웨이의 생명 게임이다. 판은 $m$ 개의 동심원 고리와 $n$ 개의 방사선으로 이루어진다. 고리는 바깥쪽부터 안쪽으로 번호가 매겨져 가장 바깥이 $0$, 가장 안쪽이 $m-1$ 이다. 각 고리는 $n$ 개의 방사선으로 나뉘므로 정확히 $n$ 개의 칸을 가진다. 각 칸은 쌍 $(r, c)$ 로 나타내며, $r$ 은 고리 번호($0 \le r \le m-1$), $c$ 는 고정된 반지름에서 시계 방향으로 센 위치($0 \le c \le n-1$)이다. 방사선의 수 $n$ 은 항상 짝수이다.

매 순간 모든 칸이 동시에 갱신되며, 일반적인 생명 게임 규칙을 따른다. 죽은 칸은 살아 있는 이웃이 정확히 3개이면 다음 세대에 살아나고, 살아 있는 칸은 살아 있는 이웃이 2개 미만이거나 3개 초과이면 죽으며, 나머지 칸은 상태를 유지한다.

모든 칸은 정확히 8개의 이웃을 가지며, 다음과 같이 정의된다(위치를 나타내는 첨자는 모두 $n$ 으로 나눈 나머지로 생각한다).

• $0 < r < m-1$ 인 내부 칸 $(r, c)$ 의 이웃은 $(r, c\pm 1)$, $(r-1, c-1)$, $(r-1, c)$, $(r-1, c+1)$, $(r+1, c-1)$, $(r+1, c)$, $(r+1, c+1)$ 의 8개이다.
• 가장 바깥 고리의 칸 $(0, c)$ 의 이웃은 보통의 5개 $(0, c\pm 1)$, $(1, c-1)$, $(1, c)$, $(1, c+1)$ 에, 같은 고리에서 정반대 위치의 칸 $(0, c + n/2)$ 와 그 양옆 $(0, c + n/2 - 1)$, $(0, c + n/2 + 1)$ 을 더한 것이다.
• 가장 안쪽 고리의 칸 $(m-1, c)$ 의 이웃은 보통의 5개 $(m-1, c\pm 1)$, $(m-2, c-1)$, $(m-2, c)$, $(m-2, c+1)$ 에, 정반대 위치의 칸 $(m-1, c + n/2)$ 와 그 양옆 $(m-1, c + n/2 - 1)$, $(m-1, c + n/2 + 1)$ 을 더한 것이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 양의 정수 $m$ 과 $n$($3 \le m \le 100$, $6 \le n \le 100$, $n$ 은 짝수)으로 시작하며, 각각 고리의 수와 방사선의 수를 뜻한다. 이어서 양의 정수 $k$ 와 서로 다른 정수 쌍 $k$ 개가 주어진다(여러 줄에 걸칠 수 있다). 각 쌍 $r\ c$ 는 처음에 살아 있는 칸의 고리 $r$ 과 위치 $c$ 를 나타낸다. 그 다음에는 음이 아닌 정수 $g$($g \le 500$)가 주어지며, 시뮬레이션할 세대 수를 뜻한다. 마지막 테스트 케이스 뒤에는 두 개의 $0$ 으로 이루어진 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 Case X:($X$ 는 $1$ 부터 시작하는 테스트 케이스 번호)에 이어 다섯 개의 정수를 출력한다. 즉, $g$ 세대 후 살아 있는 칸의 수, 사전순으로 가장 앞선 살아 있는 칸의 위치 $r_1\ c_1$, 사전순으로 가장 뒤인 살아 있는 칸의 위치 $r_2\ c_2$ 이다. 칸은 고리 번호, 그다음 칸 위치의 사전순으로 정렬한다. 살아 있는 칸이 하나도 없으면 이 다섯 정수로 0 -1 -1 -1 -1 을 출력한다.