금고 회사

주식회사 금고는 매우 안전한 금고를 만든다. 이 회사의 최신 금고는 빛을 이용한다. 직사각형 그리드에 거울을 배치하고 레이저를 발사한 뒤, 감지기로 레이저가 빠져나오는지를 확인한다.

그리드는 $r$개의 행과 $c$개의 열로 이루어져 있으며, 행은 위에서부터 $1$부터 $r$까지, 열은 왼쪽에서부터 $1$부터 $c$까지 번호가 매겨진다. 레이저는 가장 윗 행의 왼쪽에서 발사되어 칸 $(1, 1)$로 오른쪽 방향으로 들어온다. 빛이 거울이 있는 칸에 들어가면 반사되며, 모든 거울은 45도 대각선 모양으로 / 또는 \ 중 하나이다. / 거울은 오른쪽으로 가는 빛을 위쪽으로, 위쪽으로 가는 빛을 오른쪽으로 바꾼다(마찬가지로 아래쪽으로 가는 빛은 왼쪽으로). \ 거울은 오른쪽으로 가는 빛을 아래쪽으로, 아래쪽으로 가는 빛을 오른쪽으로 바꾼다(마찬가지로 위쪽으로 가는 빛은 왼쪽으로).

금고는 빛이 가장 아랫 행의 오른쪽으로, 즉 칸 $(r, c)$에서 오른쪽으로 그리드를 빠져나올 때에만 열린다. 그 밖의 모든 경우에는 알람이 울린다.

모든 금고에는 거울이 정확히 하나 빠져 있다. 즉 거울이 있어야 할 칸 하나가 비어 있다. 금고를 열려면 사용자는 빈 칸 하나에 거울 한 개를 넣는다(정당한 사용자는 비어 있는 정확한 위치와 거울의 모양을 알고 있다).

거울을 넣지 않았을 때는 열리지 않고, 빈 칸과 거울 모양을 적절히 선택하면 열 수 있는 금고를 안전한 금고라고 한다. 금고의 현재 상태가 주어질 때, 그 상태를 판정하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 금고 하나를 나타낸다. 입력은 파일의 끝에서 끝난다.

각 테스트 케이스의 첫째 줄에는 네 정수 $r$, $c$, $m$, $n$ ($1 \le r, c \le 10^6$, $0 \le m, n \le 2 \times 10^5$)이 주어진다. 금고는 $r$행 $c$열로 이루어져 있다.

다음 $m$개의 줄에는 두 정수 $r_i$와 $c_i$ ($1 \le r_i \le r$, $1 \le c_i \le c$)가 주어지며, $r_i$행 $c_i$열에 / 모양 거울이 있다는 뜻이다.

이어지는 $n$개의 줄에는 같은 형식으로 \ 모양 거울의 정보가 주어진다.

$m + n$개의 위치는 모두 서로 다르다.

각 테스트 케이스마다 Case i: (테스트 케이스 번호 $i$)를 출력한 뒤 다음을 출력한다.

• 거울을 넣지 않아도 금고가 열리면 0.
• 거울을 넣지 않으면 열리지 않는 경우 k r c. 여기서 $k$는 거울을 넣어 금고를 열 수 있는 빈 칸의 개수이고, $(r, c)$는 그러한 칸 중 사전순으로 가장 앞서는 칸이다(행이 작은 것 먼저, 그다음 열이 작은 것). 한 칸에 /와 \ 거울을 모두 넣어 열 수 있더라도 그 칸은 한 개로 센다.
• 거울을 넣어도 금고를 열 수 없으면 impossible.