골칫거리 두더지

두더지 한 마리가 우리 마당을 직사각형 격자 모양의 굴로 온통 헤집어 놓았습니다. 피해에 화가 난 우리는 두더지를 잡으려고 테리어 여러 마리를 마당에 풀어놓았습니다. 테리어는 청력이 매우 예민해서 두더지에게 충분히 가까이 다가가면 재빨리 땅을 파 두더지를 잡을 수 있습니다. 안타깝게도 두더지 역시 테리어의 발소리가 만드는 진동에 매우 민감해서, 테리어를 적극적으로 피해 다닙니다.

테리어를 풀어놓은 순간 두더지가 어디에 있었는지는 알 수 없습니다. 하지만 우리는 한동안 테리어들이 마당을 돌아다니는 모습을 지켜보았고, 그동안 두더지는 잡히지 않았습니다. 이 관찰 결과를 바탕으로 두더지가 있을 수 있는 위치를 추론하는 프로그램을 작성하세요.

관찰을 시작한 시점에, 두더지는 어떤 테리어의 바로 아래 칸에 있지도 않았고 어떤 테리어와 (가로 또는 세로로) 인접한 칸에 있지도 않았음을 알고 있습니다. 이후 각 시간 간격마다 테리어들은 제자리에 머무르거나 가로 또는 세로로 한 칸 이동할 수 있고, 그다음 두더지도 같은 방식으로 움직일 수 있습니다. 이 이동들(테리어의 이동이든 두더지의 이동이든)의 전후 어느 시점에라도 어떤 테리어가 두더지 바로 위 칸에 있거나 (가로 또는 세로로) 인접한 칸에 있게 되면, 두더지는 잡히고 맙니다.

마당의 크기와 시간에 따른 테리어들의 위치가 주어질 때, 관찰이 끝난 시점에 두더지가 있을 수 있는 모든 칸을 출력하세요.

입력은 하나 이상의 관찰 집합으로 이루어집니다. 각 관찰 집합은 다음과 같이 구성됩니다.

• 첫 번째 줄에는 네 정수 W L N T가 주어집니다. W와 L은 각각 마당의 너비(x 방향)와 길이(y 방향)를 나타내는 양의 정수입니다. N은 테리어의 수(0 이상)이고, T는 관찰한 시간 단계의 수(양의 정수)입니다.
• 이어지는 N개의 줄은 각각 테리어 한 마리를 설명합니다. 한 줄에는 2T개의 정수가 있으며, 이는 해당 테리어의 T개 시간 단계별 (x, y) 좌표를 괄호나 쉼표 없이 공백으로 구분해 나열한 것입니다. 좌표는 마당의 한 모서리인 (0, 0)부터 반대쪽 모서리인 (W, L)까지의 범위를 가집니다.

입력의 끝은 올바른 W L N T 줄 대신 네 개의 0으로 이루어진 줄로 표시됩니다.

각 관찰 집합마다 먼저 Observation Set k 줄을 출력합니다. 여기서 k는 관찰 집합의 번호이며 1부터 시작합니다.

두더지가 있을 수 있는 위치가 하나 이상 있으면, 다음 줄부터 가능한 모든 위치를 (x,y) 쌍으로 출력합니다. 한 줄에 최대 8개의 쌍을 출력하며(각 집합의 마지막 줄은 더 적을 수 있습니다), 줄의 첫 쌍 앞에는 공백이 없어야 하고 마지막 쌍 뒤에도 공백이 없어야 하며, 같은 줄의 연속된 쌍 사이는 정확히 하나의 공백으로 구분합니다. 각 쌍은 내부 공백 없이 (x,y) 형식으로 씁니다. 쌍은 y가 작은 것을 먼저, y가 같으면 x가 작은 것을 먼저 오도록 정렬해 출력합니다.

두더지가 있을 수 있는 위치가 하나도 없으면, 해당 집합의 두 번째 줄에 No possible locations 메시지를 출력합니다.

한 관찰 집합의 상황은 다음과 같이 시각화할 수 있습니다.