题目描述

地质学家有时会根据降雨的流向将一片陆地划分为不同区域，这些区域被称为流域。

给定一幅高程图（一个二维海拔数组），请按照以下规则为图中区域标注：同一流域内的所有位置标注相同的标签。

规则说明：

从每个单元格出发，水流最多流向其 4 个相邻单元格（北、西、东、南）中的一个。

对于某个单元格，若其 4 个相邻单元格中没有海拔低于当前单元格的，则水不流动，该单元格被称为汇点。 否则，水从当前单元格流向海拔最低的相邻单元格。若存在多个海拔最低的相邻单元格（即平局），水流将按以下顺序选择第一个方向：北、西、东、南。

所有直接或间接流向同一汇点的单元格属于同一流域。每个流域用唯一的小写字母标注，且需满足：将地图各行从上到下拼接后，得到的字符串字典序最小（特别地，最西北单元格所在的流域始终标注为 'a'）。注意：相邻的汇点不属于同一流域。

输入格式

输入第一行包含两个整数 H 和 W，分别表示地图的高度（行数）和宽度（列数）（1 ≤ H, W ≤ 100）。接下来 H 行，每行包含 W 个整数，按从北到南、从西到东的顺序表示各单元格的海拔（0 ≤ 海拔 < 10,000）。保证流域数量不超过 26 个。

输出格式

输出 H 行，每行对应地图中一行单元格的流域标签，顺序与输入一致。

样例数据1

input

3 3
9 6 3
5 9 6
3 5 9

output

a b b
a a b
a a a

样例1解释

右上角和左下角的单元格是汇点。对角线上的单元格水流向地势更低的左下角（5 < 6）。

样例数据2

input

1 10
0 1 2 3 4 5 6 7 8 7

output

a a a a a a a a a b

样例数据3

input

2 3
7 6 7
7 6 7

output

a a a
b b b

样例数据4

input

5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9

output

a a a a a
a a b b a
a b b b a
a b b b a
a a a a a