6. Obnova bytového parku

Nie je tomu tak dávno, čo sa lokálny magnát (volajme ho M) rozhodol odkúpiť od mesta nejaké paneláky a zrekonštruovať byty v nich. Samozrejme, najlepší spôsob, ako s takýmto biznisom začať, je podať si grant. Ako to už však chodí, na získanie grantu potrebujete splniť absurdné požiadavky. Ani tentoraz nedošlo k výnimke a magnát M sa musel popasovať hneď s niekoľkými:

• Počet kúpených panelákov musí byť práve \(k\).

• Paneláky sa musia nachádzať v štvrti, kde sú budovy usporiadané do štvorčekovej siete, teda všetky majú rovnako veľký, štvorcový pôdorys.

• Všetky kúpené paneláky spolu musia susediť stenami.

• Čím je stavba nižšia, tým viac je ekologická a teda vhodnejšie vyvažuje charakter mesta.

• Mačka musí mať štyri nohy a nestrká sa do mikrovlnky.

Aj magnátovi M chvíľu trvalo, kým pochopil, o čo sa tu jedná. Zistil, že úradníci si od neho vyúčtujú ekologický poplatok, na základe toho, akú najvyššiu budovu bude rekonštruovať.

Jeho cieľom je teda splniť všetky podmienky a zároveň spraviť čo najvýhodnejší biznis – vybrať si takých \(k\) bytoviek, že vytvoria súvislú oblasť a najvyššia budova medzi nimi je čo najnižšia (medzi všetkými takýmito oblasťami).

Úloha

Dostanete číslo \(k\) a mriežku čísel s \(r\) riadkami a \(s\) stĺpcami.

Hovoríme, že oblasť mriežky je súvislá, ak sa vieme z každého jej políčka dostať na každé iné políčko oblasti len prechodmi smermi hore, dole, vpravo, vľavo, bez opustenia danej oblasti.

Nájdite takú súvislú oblasť, ktorá obsahuje \(k\) čísel a najväčšie číslo, ktoré obsahuje, je najmenšie možné.

Formát vstupu

Na prvom riadku sa nachádza číslo \(k\). Na druhom riadku sú medzerou oddelené čísla \(r, s\). Pre všetky vstupy platí \(1 \le k \le r \cdot s \le 10^6\).

Na každom z nasledujúcich \(r\) riadkov sa nachádza \(s\) medzerou oddelených kladných celých čísel, ktoré udávajú výšky jednotlivých budov v meste. Výška žiadnej budovy nepresiahne \(10^9\).

Formát výstupu

Na prvý riadok výstupu vypíšte celé číslo určujúce najmenšiu možnú výšku najvyššej odkúpenej budovy. Následne vypíšte \(r\) riadkov a na každom z nich \(s\) znakov. Každý znak musí byť bodka ("."), alebo hviezdička ("*"), pričom hviezdičkami označené políčka musia vyznačovať ľubovoľné zo správnych riešení.

Príklady

Input:

6
4 3
2 3 4
2 3 2
5 1 1
3 2 1

Output:

3
...
..*
.**
***

Input:

4
3 3
1 1 2
1 2 1
2 1 1

Output:

2
***
.*.
...