레이팅 미적용Safe Ltd.는 고품질(hi\(gh-qu\)ality) 금고를 제조하는 회사이다. 이 회사의 최신 발명품은 여러 거울이 있는 직사각형 격자를 통과하는 레이저 빔을 이용하는 광학 잠금장치이다. @@ @@ @@ @@ - - Laser Detector 빔이 감지됨, 금고 열림 @@ @@ @@ @@ - - Laser Detector 빔이 감지되지 않음, 경보 발생 레이저가 켜지면 빔이 격자 맨 윗 행에 왼쪽에서 수평으로 들어온다. 빔은 부딪히는 모든 거울에 반사된다. 각 거울은 45도 대각선 방향, 즉 ⧸또는 ⧹으로 놓여 있다. 빔이 격자 맨 아랫 행에서 오른쪽으로 수평으로 나가면 감지되어 금고가 열린다(위 그림의 왼쪽 참조). 그렇지 않으면 금고는 닫힌 채로 있고 경보가 울린다. 각 금고에는 빠진 거울이 하나 있어서 레이저 빔이 격자를 성공적으로 통과하지 못한다(위 그림의 오른쪽 참조). 금고에는 사용자가 빈 격자 칸 아무 곳에나 거울 하나를 넣을 수 있는 장치가 있다. 정당한 사용자는 빠진 거울의 올바른 위치와 방향(위에서는 4행 3열의 ⧸)을 알고 있으므로 금고를 열 수 있다. 이 지식이 없는 사용자는 올바르게 추측해야 하는데, 격자가 큰 금고에서는 이것이 어려울 수 있다. 당신의 일은 특정 금고들이 실제로 안전한지 판별하는 것이다. 안전한 금고란 거울을 넣지 않고는 바로 열리지 않으면서, 빠진 거울의 유효한 위치와 방향이 적어도 하나 존재하는 금고이다. 그런 위치와 방향이 실제로 여러 개 있을 수도 있다.
각 테스트 케이스는 금고 하나를 설명하며, 네 정수 \(r\), \(c\), \(m\), \(n\) (\(1 \le r\), \(c \le 1\,000\,000\), \(0 \le m\), \(n \le 200\,000\))이 있는 줄로 시작한다. 장치의 격자는 \(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\)개 위치는 쌍마다 서로 다르다.
각 테스트 케이스마다 케이스 번호와 함께 다음을 출력한다.
-
거울을 넣지 않아도 금고가 열리면 0.
-
거울을 넣지 않으면 금고가 열리지 않고, 거울을 넣으면 금고가 열리는 위치가 정확히 \(k\)개 있으며, (r, c)가 그중 사전순으로 가장 작은 행, 열 위치라면 \(k\) \(r\) \(c\). ⧸거울과 ⧹거울 모두로 금고가 열리는 위치는 한 번만 센다.
-
거울을 넣든 안 넣든 금고를 열 수 없으면 impossible.
5 6 1 4
2 3
1 2
2 5
4 2
5 5
100 100 0 2
1 77
100 77
100 100 0 0
Case 1: 2 4 3
Case 2: 0
Case 3: impossible