이중 시야

어느 회사는 사람과 기계가 모두 쉽게 읽을 수 있는 잉크와 글꼴을 설계한다. 글꼴은 직사각형 격자 위에 그린다. 아래는 처음 다섯 개의 숫자를 나타낸 간단한 5×3 도안이다.

. o .     . o .    oo .    oo .    o . o
o . o    . o .    . . o    . . o    o . o
o . o    . o .    . o .    oo .    ooo
o . o    . o .    o . .    . . o    . . o
. o .     . o .    ooo    oo .    . . o

잉크는 평범한 검은색 잉크처럼 보이지만, 표면 바로 아래에는 적외선 스캐너로만 감지할 수 있는 특수 고분자(폴리머)가 함께 들어 있다. 사람은 검은 잉크만 보고 폴리머는 보지 못하며, 기계는 폴리머만 보고 검은 잉크는 보지 못한다. 폴리머는 잉크보다 훨씬 비싸기 때문에 회사는 폴리머를 최대한 적게 쓰고 싶어 한다. 많은 글꼴에서 각 기호는 많아야 두 개의 픽셀만으로 유일하게 구별할 수 있다는 사실이 알려져 있다. 기호마다 픽셀 한두 개에만 폴리머를 입히면 스캐너의 정확도를 100%로 유지하면서도 비용을 크게 줄일 수 있다. 위 글꼴은 이런 성질을 가지며, 각 기호를 유일하게 구별해 주는 픽셀은 # 로 표시되어 있다. (다른 선택도 가능하다.)

. # .     . o .    #o .    oo .    o . #
# . o    . # .    . . o    . . o    o . o
o . o    . o .    . o .    #o .    ooo
o . o    . o .    # . .    . . o    . . o
. o .     . o .    ooo    #o .    . . o

주어진 글꼴이 이런 성질을 가지는지 판단하고, 가진다면 구별용 픽셀을 표시하는 프로그램을 작성하라.

입력은 하나 이상의 테스트 케이스로 이루어지며, 마지막에는 입력의 끝을 나타내는 0 0 0 (세 개의 0) 한 줄이 온다.

각 테스트 케이스는 공백으로 구분된 세 양의 정수 n, r, c 가 적힌 줄로 시작한다. n 은 글꼴에 있는 기호의 개수, r 은 각 격자의 행 수, c 는 각 격자의 열 수이다. 이어지는 r 개의 줄에는 기호들의 그림이 예시와 똑같은 형식으로 주어진다. 점 . 은 빈 칸, 소문자 o 는 픽셀을 뜻하며, 인접한 격자는 공백 하나로 구분된다. 각 줄의 너비는 (줄 끝 문자를 제외하고) 최대 79글자이고, r 은 최대 10이다. 테스트 케이스 번호는 1부터 시작한다.

테스트 케이스 i 에 대해 먼저 Test i 라는 줄을 출력한다. 그런 다음 모든 기호를 픽셀 한두 개로 유일하게 구별할 수 있는지 판단한다. 구별할 수 없는 기호가 하나라도 있으면 impossible 이라는 단어 한 줄을 출력한다. 그렇지 않으면 각 기호의 구별용 픽셀을 # 로 바꿔 출력하고 나머지는 같은 형식으로 글꼴을 출력한다.

일반적으로 한 기호를 유일하게 구별하는 픽셀이나 픽셀 쌍은 여러 개일 수 있으므로, 답을 하나로 정하기 위해 다음 규칙을 둔다. 두 픽셀을 비교할 때 가장 위-왼쪽 픽셀이란 격자에서 더 위쪽에 있는 픽셀을 말하며, 둘이 같은 행에 있으면 더 왼쪽에 있는 픽셀을 말한다.

• 픽셀 하나로 충분하면, 조건을 만족하는 가장 위-왼쪽 픽셀을 표시한다.
• 픽셀 하나로 해결되는 경우에는 절대로 두 픽셀 해를 쓰지 않는다.
• 픽셀 두 개가 필요하면, 첫 번째 픽셀이 가장 위-왼쪽인 쌍을 고른다. 첫 번째 픽셀이 같은 쌍이 여럿이면 두 번째 픽셀이 가장 위-왼쪽인 쌍을 고른다.

한 픽셀은 같은 위치에 픽셀을 가진 다른 기호가 없을 때 그 기호를 유일하게 구별하며, 픽셀 쌍은 두 위치 모두에 픽셀을 가진 다른 기호가 없을 때 그 기호를 유일하게 구별한다.