题目描述

在夜空高处，闪烁的星星以各种形状的星群出现。**星群（Cluster）**定义为一组非空的相邻星星，相邻指水平、垂直或对角线方向相连。每个星群不能是更大星群的一部分。

星群可能具有相似性。若两个星群的形状和星星数量相同（不论方向如何），则称它们是相似的。通常，一个星群可能的方向有8种，如图1所示。

夜空由一张星空图表示，这是一个由0和1组成的二维矩阵。单元格为1表示有星星，0表示无星星。

给定一张星空图，用小写字母标记所有星群：相似星群必须用相同字母标记，非相似星群用不同字母。标记方式是将星群中的每个1替换为对应的小写字母。字母的分配顺序取决于不同星群的首次出现顺序（按从上到下、从左到右的顺序）。

输入

程序从标准输入读取数据：

• 前两行分别包含星空图的宽度$W$和高度$H$。
• 接下来的$H$行，每行包含$W$个字符，表示星空图（0或1）。

约束条件：

• $0 \leq W \leq 100$（星空图宽度）
• $0 \leq H \leq 100$（星空图高度）
• $0 \leq \text{星群数量} \leq 500$
• $0 \leq \text{非相似星群数量} \leq 26$（仅用a-z标记）
• $1 \leq \text{每个星群的星星数量} \leq 160$

输出

程序向标准输出写入处理后的星空图：

• 所有星群中的1被替换为对应的小写字母，0保持不变。
• 相似星群用相同字母，非相似星群用不同字母，字母按首次出现顺序分配。

输入数据 1

23  
15  
10001000000000010000000  
01111100011111000101101  
01000000010001000111111  
00000000010101000101111  
00000111010001000000000  
00001001011111000000000  
10000001000000000000000  
00101000000111110010000  
00001000000100010011111  
00000001110101010100010  
00000100110100010000000  
00010001110111110000000  
00100001110000000100000  
00001000100001000100101  
00000001110001000111000  

输出数据 1

a000a0000000000b0000000  
0aaaaa000ccccc000d0dd0d  
0a0000000c000c000dddddd  
000000000c0b0c000d0dddd  
00000eee0c000c000000000  
0000e00e0ccccc000000000  
b000000e000000000000000  
00b0f000000ccccc00a0000  
0000f000000c000c00aaaaa  
0000000ddd0c0b0c0a000a0  
00000b00dd0c000c0000000  
000g000ddd0ccccc0000000  
00g0000ddd0000000e00000  
0000b000d0000f000e00e0b  
0000000ddd000f000eee000  

提示

需要注意的是，此样例输入对应星空图的可视化效果如图所示，样例输出则是标记后的结果。