별이 빛나는 밤

밤하늘 높이, 빛나는 별들은 다양한 모양의 무리를 이루어 나타난다. 무리(cluster) 는 가로, 세로, 또는 대각선 방향으로 인접한 별들이 모인 비어 있지 않은 집합이다. 무리는 극대(maximal)이다. 즉, 더 큰 무리의 일부가 될 수 없다.

서로 다른 무리가 닮은(similar) 관계일 수 있다. 두 무리는 방향(회전·대칭)에 관계없이 모양과 별의 개수가 같으면 닮았다고 한다. 일반적으로 하나의 무리는 여덟 가지 방향으로 나타날 수 있다(네 가지 회전 각각에 대해 좌우 대칭 여부). 아래 그림이 그 예이다.

여덟 개의 닮은 무리.

밤하늘은 하늘 지도(sky map) 로 표현되며, 이는 0과 1로 이루어진 2차원 행렬이다. 각 칸은 별이 있으면 1, 없으면 0이다.

각 무리를 하나의 소문자로 표시한다. 즉, 그 무리에 속한 모든 1을 해당 소문자로 바꾼다. 닮은 무리끼리는 같은 문자로, 닮지 않은 무리끼리는 서로 다른 문자로 표시해야 한다.

첫째 줄에 하늘 지도의 너비 $W$가, 둘째 줄에 높이 $H$가 주어진다. 이어지는 $H$개의 줄에 하늘 지도가 주어지며, 각 줄은 정확히 $W$개의 문자(0 또는 1)로 이루어진다.

• $0 \le W \le 100$
• $0 \le H \le 100$
• $0 \le$ 무리의 개수 $\le 500$
• $0 \le$ 닮지 않은 무리의 개수 $\le 26$ (문자 a..z)
• $1 \le$ 한 무리에 속한 별의 개수 $\le 160$

모든 무리를 표시한 하늘 지도를 출력한다. 답을 유일하게 만들기 위해 다음 규칙으로 문자를 배정한다.

지도를 행 우선 순서(위에서 아래로, 각 줄에서는 왼쪽에서 오른쪽으로)로 훑는다. 아직 어떤 무리에도 속하지 않은 별을 처음 만나면, 그 별에서 새로운 무리가 시작되며 그 무리의 모양을 구한다. 모양과 문자의 대응은 처음 나타난 순서대로 만든다. 즉, 처음 등장한 모양은 a, 그다음에 새로 등장한 모양은 b, 그다음은 c, … 로 표시한다. 어떤 무리의 모양이 이미 앞에서 나타났다면(앞선 무리와 닮았다면) 그 모양에 배정된 문자를 다시 사용한다.

각 무리의 모든 1을 배정된 문자로 바꾸어 $H$개의 줄을 출력한다.

아래 예제의 하늘 지도는 너비 23, 높이 15이다. 이 지도는 다음과 같은 밤하늘 그림에 해당한다.

밤하늘 그림.

무리를 모두 표시하면 그림은 다음과 같아진다.

무리를 표시한 그림.