5. Otepľovanie v Absurdistane

Ako iste viete, v dôsledku globálneho otepľovania sa topia ľadovce a kvôli tomu stúpajú hladiny oceánov. V niektorých nízko položených krajinách, ako je napríklad Absurdistan, to potom spôsobuje problémy. So stúpajúcou hladinou mora totiž stúpa hladina podzemnej vody a – keďže Absurdistan má veľmi priepustné podložie – s ňou aj hladina nadzemnej vody. A tak postupne v rôznych kotlinách, údoliach a priehlbinách vznikajú nové jazerá, ktorým Absurdistanci vymýšľajú nové názvy.

Úloha

Absurdistan má tvar obdĺžnika, ktorý si pre účely tejto úlohy rozdelíme na \(r \times s\) políčok. Každé políčko má svoju nadmorskú výšku¹ – celé číslo z rozsahu \(0\) až \(H\). Hladina podzemnej vody je na začiatku \(0\). Každý rok hladina vody stúpne o \(1\) a všetky políčka, ktoré sa ocitli pod hladinou (ich nadmorská výška je ostro menšia ako výška hladiny), sa zatopia.

Každé zatopené políčko v Absurdistane je oficiálne súčasťou nejakého jazera. Pre jednoduchosť predpokladajme, že názvy Absurdistanských jazier sú nezáporné celé čísla. Každý rok sa v Absurdistane zíde Kartografická Spoločnosť Patriotov a každému zatopenému políčku \(P\) určí, ktorého jazera je súčasťou, podľa nasledujúcich pravidiel:

• Každé políčko, ktoré bolo zatopené už aj rok predtým, ostáva súčasťou jazera, ku ktorému patrilo doteraz.

• Pre každé novozatopené políčko \(P\) skúsime nájsť políčko \(R\) také, že \(R\) bolo zatopené už aj pred rokom, z \(P\) sa dá dostať do \(R\) idúc iba po zatopených políčkach (pričom z jedného políčka vieme vždy ísť iba na políčka susediace stranou, ale nie na políčka susediace rohom) a cesta po vode z \(P\) do \(R\) je najkratšia možná. Políčko \(P\) sa stane súčasťou rovnakého jazera ako \(R\). Ak je viacero možných políčok \(R\), vyberieme také, ktorého jazero má najmenšie číslo.

  Ak sa z \(P\) nedá po vode dostať na žiadne políčko, ktoré bolo zatopené už pred rokom, políčko \(P\) a všetky zatopené políčka, na ktoré sa z \(P\) dá dostať, budú prehlásené za novovzniknuté jazero.

• Novovzniknutým jazerám sa názvy priradia nasledovne: Prechádzame cez všetky políčka obdlžníka, pričom postupujeme po riadkoch zhora nadol, a v rámci riadka zľava doprava. Vždy, keď nájdeme zatopené políčko patriace k nejakému novovzniknutému jazeru, ktoré ešte nemá názov, toto jazero nazveme najmenším nepoužitým nezáporným celým číslom.

Všimnite si, že keď sa v dôsledku stúpania hladiny dve jazerá zlejú do jednej súvislej vodnej plochy, oficiálne sú to stále dve rôzne jazerá s presne vymedzenými hranicami. Pre lepšie pochopenie týchto pravidiel si môžete pozrieť vzorový príklad s vysvetlením.

Vašou úlohou bude pre každé políčko zistiť číslo jazera, ku ktorému bude toto políčko patriť po \(H+1\) rokoch, teda keď už bude celý Absurdistan zatopený.

Formát vstupu

V prvom riadku vstupu sú dve kladné celé čísla \(r, s \,(r \cdot s \leq 250\,000)\) – počet riadkov a počet stĺpcov obdĺžnika. V druhom riadku je jedno kladné celé číslo \(H \,(H \leq 250\,000)\). Nasleduje \(r\) riadkov, každý z nich obsahuje \(s\) medzerami oddelených celých čísel z rozsahu \(0\) až \(H\) – nadmorské výšky jednotlivých políčok.

Formát výstupu

Vypíšte \(r\) riadkov a v každom z nich \(s\) medzerami oddelených čísel: čísla jazier, ku ktorým budú patriť jednotlivé políčka po úplnom zatopení Absurdistanu.

Príklad

Input:

8 8
4
3 1 1 1 2 2 0 0
3 1 2 2 2 0 2 1
0 0 2 2 1 0 2 1
0 0 2 2 1 2 2 1
1 3 2 2 1 1 1 1
4 4 3 3 4 4 4 4
0 0 4 3 2 1 2 0
4 0 4 2 1 0 0 3

Output:

2 2 2 2 2 0 0 0
2 2 2 2 1 1 0 0
2 2 2 1 1 1 0 0
2 2 2 1 1 1 0 0
2 1 1 1 1 1 0 0
2 1 1 1 1 1 0 0
3 3 1 5 5 5 4 4
3 3 3 5 5 5 5 4

Absurdistan bude po jednotlivých rokoch vyzerať nasledovne (modré oblasti sú zatopené, pričom svetlomodré sú novozatopené. Čísla v nezatopených políčkach udávajú nadmorskú výšku, čísla v zatopených udávajú číslo jazera):