#!/usr/bin/env python
# coding: utf-8

# # Watershedsに挑戦（問題編）

# Google code jam 2009 qualification roundのB問題[watersheds](https://code.google.com/codejam/contest/90101/dashboard#s=p1)に挑戦する．

# この問題では以下の設定が与えられている．
# 
# * 南北$H$マス，東西$W$マスの区画が，その標高とともに与えられている．
# * ある区画に水が流れ込んだら，その区画よりも低い隣接区画に流れ出ていく．隣接区画は東西南北に隣接する4つの区画とする．
# * ある区画よりも低い隣接区画が複数ある場合には，最も標高の低い隣接区画に流れていくとする．
# * 最も標高の低い隣接区画が複数ある場合には，北，西，東，南の順に優先的に流れていくとする．
# * ある区画よりも低い隣接区画がないならば，その区画からは水は流れ出ない．そのような区画を池とよぶことにする．
# * 水が最終的に流れ込む池ごとに区画を分類し，ラベル付けすることを考える．
# 
# 以上の設定のもとで，この問題を定義する．
# 
# この問題を入力と出力で定義すると
# 
# * 入力: $H$行$W$列の行列$A = (a_{ij})$，ただし$a_{ij} \in \mathbb{Z}_{\ge 0}$であり行列のそれぞれの要素は各区画の標高に対応
# * 出力: 水が流れ込む池ごとにラベル付けされた$H$行$W$列の行列$B$，ただしラベルは文字列$(b_{1,1}, b_{1,2}, \dots, b_{1,W}, b_{2,1},\dots, b_{H,W}$が辞書順最小になるもの
# 
# である．
# 
# なお，この問題では，高々26個の池が出力となるような入力が与えられる．

# Small datasetの入力は$1 \le H, W \le 10$，$0 \le a_{ij} < 10$，池は高々2個である．
# 
# Large datasetの入力は$1 \le H, W \le 100$，$0 \le a_{ij} < 10000$，池は高々26個である．

# 入力と，それに対する正しい出力の例は
# 
# * 入力が$\begin{pmatrix} 9 & 6 & 3 \\ 5 & 9 & 6 \\ 3 & 5 & 9 \end{pmatrix}$ならば，出力は$\begin{pmatrix} a & b & b \\ a & a & b \\ a & a & a \end{pmatrix}$，
# * 入力が$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 7 \end{pmatrix}$ならば，出力は$\begin{pmatrix} a & a & a & a & a & a & a & a & b \end{pmatrix}$，
# * 入力が$\begin{pmatrix} 7 & 6 & 7 \\ 7 & 6 & 7 \end{pmatrix}$ならば，出力は$\begin{pmatrix} a & a & a \\ b & b & b \end{pmatrix}$，
# 
# などなどである．