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[^1] – 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):

1. Pre jednoduchosť, za nadmorskú výšku budeme považovať nadmorskú výšku na začiatku zatápania, nie výšku nad aktuálnou hladinou mora. Nadmorská výška v našom chápaní sa teda počas zatápania meniť nebude.↩