Starry Night

High up in the night sky, the shining stars appear in clusters of various shapes. A cluster is a non-empty group of neighbouring stars that are adjacent horizontally, vertically, or diagonally. A cluster is maximal: it cannot be part of a larger cluster.

Clusters may be similar. Two clusters are similar if they have the same shape and the same number of stars, regardless of orientation. In general a cluster can appear in eight orientations (four rotations, each optionally mirrored), as illustrated below.

Eight similar clusters.

The night sky is represented by a sky map, a two-dimensional matrix of 0s and 1s. A cell holds 1 if it contains a star and 0 otherwise.

Mark every cluster with a lower-case letter by replacing each 1 of the cluster with that letter. Similar clusters must be marked with the same letter; clusters that are not similar must be marked with different letters.

The first line contains the width $W$ of the sky map; the second line contains its height $H$. The next $H$ lines contain the sky map, each with exactly $W$ characters (0 or 1).

• $0 \le W \le 100$
• $0 \le H \le 100$
• $0 \le$ number of clusters $\le 500$
• $0 \le$ number of non-similar clusters $\le 26$ (letters a..z)
• $1 \le$ number of stars per cluster $\le 160$

Print the sky map with every cluster marked. To make the answer unique, assign the letters as follows.

Scan the map in row-major order (top to bottom, and within each row from left to right). The first time you reach a star that does not yet belong to a marked cluster, that star begins a new cluster; determine the cluster's shape. Keep a mapping from shapes to letters built in order of first appearance: the first distinct shape encountered is marked a, the next new distinct shape b, then c, and so on. Whenever a cluster's shape has already appeared (it is similar to an earlier cluster), reuse that shape's letter.

Replace every 1 of each cluster with its assigned letter and print the resulting $H$ lines.

The example below has a sky map of width 23 and height 15. This map corresponds to the following picture of the sky.

Picture of the sky.

After all clusters are marked, the picture becomes:

Picture with the clusters marked.