Constellation Marking

The night sky can be represented as a sky map, which is a 2D matrix composed of characters 0 and 1. Here, the character 1 indicates that there is a star at that location, while 0 indicates an empty space. A constellation is defined as a connected set of stars. Two stars are considered connected if they are adjacent horizontally or vertically (i.e. using 4-connectivity). Thus, a constellation is a connected component of 1’s in the grid.

Two constellations are said to be similar if they have the same shape up to translation. In other words, if after subtracting the minimum row and column indices from the coordinates of the stars in the constellation, the resulting sets of coordinates are identical, they are considered similar.
Formally, if a constellation has star positions \(\{(r_1,c_1), (r_2,c_2), \ldots, (r_k,c_k)\}\), then its normalized shape (after translation) is
\[ \{(r_1-\min_i\,r_i,\; c_1-\min_i\,c_i),\; (r_2-\min_i\,r_i,\; c_2-\min_i\,c_i),\; \ldots,\; (r_k-\min_i\,r_i,\; c_k-\min_i\,c_i)\}\] \]

Your task is to mark all similar constellations with the same lowercase letter. Different (non-similar) constellations should be marked with different letters. To mark a constellation, replace every 1 in that constellation with the corresponding lowercase letter. All empty positions (originally 0) should remain unchanged.

The input begins with two integers N and M representing the number of rows and columns respectively, followed by N lines of a M-character string. The output should be the transformed sky map.

inputFormat

The first line contains two space-separated integers N and M (1 ≤ N, M ≤ 1000), representing the dimensions of the sky map. The following N lines each contain a string of M characters, each being either 0 or 1.

outputFormat

Output the sky map after marking the constellations. For each constellation (connected component of 1's using 4-connectivity), replace every 1 with a lowercase letter. Similar constellations (those with identical normalized shapes) should be marked with the same letter, and different ones with different letters. Positions originally 0 should remain 0.

sample

2 2
11
11

aa
aa