정사각형 방

Bob Roberts는 Erauqs라는 고대 민족의 건물을 연구하는 고고학자이다. 이 민족은 막대한 보물과 독특한 방 배치로 알려져 있었다. 건물은 항상 직사각형이고, 건물 안의 방은 항상 정사각형이다. (이 성질을 유지하기 위해 건물의 일부 영역은 암석으로 채워져 있었다.)

Bob은 매몰된 Erauqi 건물의 흔적을 발견하면, 발굴 전에 초음파 장비로 배치를 최대한 파악한다. 초음파로는 보물과 암석의 위치를 알 수 있지만, 벽의 위치를 찾을 만큼 정확하지는 않다. 그런데 Erauqs는 모든 정사각형 방에 보물을 정확히 하나씩 넣었으므로, 이 사실로 벽의 위치를 알아낼 수 있다. 예를 들어 초음파 결과가 그림 I.1의 왼쪽과 같다면, 가능한 방 배치는 오른쪽뿐이다.

그림 I.1: 초음파 결과와 벽의 위치

가끔 Bob은 경쟁 부족인 Elgnatcer의 건물을 발견한다. 이 경우 Erauqi 건축 원칙에 맞는 방 배치는 존재하지 않는다.

Bob은 정사각형 Erauqi 보물방의 벽 위치를 찾고 Erauqi가 아닌 건물을 식별하는 프로그램을 작성해 달라고 부탁했다. 이 문제로 Bob은 골머리를 앓고 있다.

첫 줄에 건물 격자의 행 수와 열 수를 나타내는 두 정수 n, m (1 ≤ n, m ≤ 100)이 주어진다. 이어서 각 줄에 m개의 문자로 이루어진 n줄이 주어진다. 문자는 보물을 뜻하는 '$', 암석을 뜻하는 '#', 빈 공간을 뜻하는 '.' 중 하나이다. 보물은 최소 1개, 최대 52개이다.

각 테스트 케이스에 대해, 빈 공간 전체를 각 방에 보물이 정확히 하나씩 들어가도록 정사각형 방으로 나눌 방법이 없으면 elgnatcer를 출력한다. 그렇지 않으면 Erauqi 건물의 배치를 나타내는 n×m 격자를 출력한다. 각 정사각형 방에는 'A', 'B', 'C', ..., 'Z', 'a', ..., 'z' 순서로 글자를 붙인다. 글자는 맨 윗줄(입력의 첫 줄)부터 왼쪽에서 오른쪽으로 격자를 훑으면서, 아직 글자가 없는 방을 처음 만날 때마다 다음 글자를 붙여 정한다. 출력 격자의 각 칸은 그 방의 글자이거나, 암석이면 '#'이다.