C - Najkrajšia MMSka

Danko má už v otázke najkrajšej SMSky jasno. Ale čo taká MMSka? V MMSkách sa často posielajú obrázky, ktoré sú malé, hranaté a nedá sa často s nimi nič praktické spraviť. Preto si Danko vymyslel nasledujúci formát, ktorý by sa na prenos obrazu MMSiek mohol použiť:

Každý obrázok by musel byť štvorcový a jeho strana by musela mať rozmer rovný niektorej prirodzenej mocnine čísla dva, čiže napríklad 2, 4, 8, 16, 32 atď. Obrázok by bol uložený podľa nasledujúcich pravidiel:

1. Ak je celá štvorcová skúmaná plocha obrázka rovnakej farby, tak sa číselná hodnota tejto farby zapíše do pamäte.
2. Ak nie je celá štvorcová skúmaná plocha rovnakej farby, tak sa do pamäte zapíše znak + (plus), plocha sa rozdelí na štyri menšie štvorce a krok 1 sa vykoná postupne pre každý z nich v následujúcom poradi: ľavý horný štvorec, pravý horný štvorec, pravý dolný štvorec, ľavý dolný štvorec

Algoritmus sa začína zavolaním kroku 1 na celý obrázok.

Takýto formát je naozaj krásny, lebo má veľa veľmi zaujímavých praktických vlastností. Danko bol z toho celý nadšený a pustil sa do písania vlastného firmvéru pre mobilné telefóny, ktorý by dokázal posielať MMSky práve v tomto formáte. Uvedomil si však, že posielanie obrázku nestačí. Často chce človek na neho niečo napísať alebo dokresliť. Rozhodol sa teda, že MMSka bude obsahovať viac takýchto obrázkov, ktoré sa v telefóne adresáta poskladajú na seba ako vrstvy. Adresát potom môže ľahko nahradiť napríklad vrstvu s textom nejakou s vlastným textom a MMSku kľudne poslať ďalej. Výhod oproti jednej vrstve je naozaj neúrekom.

Úloha

Danko už napísal firmvér, ktorý dokáže MMSku poslať a prijať, no má problém so zlúčením všetkých vrstiev do jednej. Napíšte mu preto program, ktorý načíta všetky vrstvy v MMSke a zlúči ich do jednej výslednej, ktorá sa následne môže zobraziť na displeji. Pri zlučovaní platí pravidlo, že vrstva, ktorá sa na vstupe objaví skor je prekrytá vrstvou, ktorá sa na vstupe objaví neskôr. Farba s hodnotou 0 sa pokladá za priesvitnú a na mieste pixelov s touto farbou sa ponechajú pixely pôvodné. Každá vrstva môže mať iné rozmery, vždy však budú menšie alebo rovné rozmerom výstupného obrázka. V prípade, že vrstva má menšie rozmery ako výstupný obrázok, treba vrstvu zväčšiť na rozmery obrázku. Zväčšovanie prebieha jednoduchým roztiahnutím do oboch smerov. Pozadie pred pridaním prvej vrstvy má celé farbu s hodnotou 0.

Vstup

Výstup

Príklad

Vstup:

2 128
64 + 0 255 0 255
128 + + 255 0 255 0 + 0 128 0 128 + 255 0 255 0 + 0 128 0 128

Výstup:

128 + + 255 0 255 0 + 255 128 255 128 + 255 0 255 0 + 255 128 255 128

Poznámka: