Watersheds (Small)

Geologists divide an area of land into regions by where rainfall flows down to. Each region is a drainage basin.

You are given an elevation map, a two dimensional array of altitudes. Label the map so that cells in the same drainage basin carry the same label, under these rules.

• From each cell, water flows down to at most one of its 4 neighboring cells (north, west, east, south).
• If no neighbor of a cell has a lower altitude than the cell itself, water does not flow out of it. That cell is a sink.
• Otherwise water flows from the cell to the neighbor with the lowest altitude.
• When several neighbors tie for the lowest altitude, water picks the first of them in this order: north, west, east, south.

Every cell that drains directly or indirectly into the same sink belongs to the same drainage basin, and a sink belongs to its own basin. Label each basin with a distinct lower case letter so that concatenating the rows of the labeled map from top to bottom gives the lexicographically smallest string. The basin of the north western cell is therefore always labeled a.

The first line contains the number of maps $T$.

Each map begins with a line holding two integers $H$ and $W$, the height and the width of the map in cells. The next $H$ lines describe the rows of the map from north to south. Each of those lines holds $W$ integers, given from west to east, which are the altitudes of the cells.

Limits

• $1 \le T \le 100$
• $1 \le H, W \le 20$
• $0 \le$ altitude $\le 9$
• every map has at most 26 drainage basins

For each map print $1 + H$ lines. The first line is

Case #X:

where $X$ is the number of the map, counting from 1. The next $H$ lines hold the basin labels of the cells in the same order as the input, one line per map row, with a single space between the labels on a line.

In the first example the upper right corner and the lower left corner are sinks. Water on the diagonal flows toward the lower left because 5 is lower than 6.