Watersheds (Large)

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

You are given an elevation map, a two dimensional array holding the altitude of every cell. Label every cell of the map so that cells in the same drainage basin get the same label, under these rules.

• Water in a cell flows down into at most one of its 4 neighboring cells.
• If no neighboring cell of a cell has a lower altitude than that cell, the water does not flow. Such a cell is a sink.
• Otherwise the water flows from the cell to the neighbor with the lowest altitude.
• If several neighbors share the lowest altitude, the water takes the first of those directions in the order North, West, East, South.

Every cell that drains to the same sink, directly or through other cells, belongs to the same drainage basin. Each basin gets one distinct lower case letter as its label, assigned so that the string formed by concatenating the rows of the map from top to bottom is lexicographically smallest. In particular, the basin of the most north western cell is always labeled 'a'.

The first line contains the number of maps $T$. Then $T$ maps follow. The first line of each map contains the height $H$ and the width $W$ of the map in cells. The next $H$ lines each hold one row of the map, from north to south, and each of those lines holds $W$ altitudes from west to east, separated by single spaces.

• $1 \le T \le 100$
• $1 \le H \le 100$, $1 \le W \le 100$
• Every altitude is an integer from $0$ to $9999$.
• A single map has at most 26 drainage basins.

For each map print $H+1$ lines. The first line has the form

Case #X:

where $X$ is the map number, starting from 1. The next $H$ lines list the basin label of every cell, in the same order as the cells appear in the input. Labels on one line are separated by a single space.

In the first map of the first example, the north eastern and south western corners are sinks. Water on the diagonal flows toward the lower altitude (5 rather than 6), so it reaches the south western sink.