5. Zajovo umenie

Mišo ukázal Zajovi, aká rýchla je jeho grafická knižnica napísaná v jazyku Go:

“Pozri, ako rýchlo vygenerujem veľa náhodných čiernych a bielych štvorcov!”, povedal Mišo a hneď sa mu na obrazovke zjavili čierne a biele štvorčeky.

“Hmm, to bolo rýchle. Ale bolo to naozaj náhodné?” začudoval sa Zajo.

“Pozri, spustím to ešte raz a bude to vyzerať inak.”, povedal Mišo a tak aj spravil. Nový obrázok vyzeral naozaj inak.

“No, niečo sa zmenilo, ale čo tie dva veľké štvorce, jeden čierny a jeden biely? Také tam boli aj minule.” poznamenal Zajo.

“No dobre, ono to nie je celkom náhodné. Najprv si rozdelím celý štvorec na štvrtiny, náhodne jednu vyfarbím na bielo, jednu na čierno a ostatné dve rekurzívne rovnako.” priznal sa Mišo.

Zajo sa na chvíľu zamyslel a opýtal sa Miša: “Ak by som ti dal čiernobiely obrázok, aký najpodobnejší obrázok by k nemu dokázal tvoj postup vygenerovať?”.

Mišo pohotovo odvetil: “Tak to teda neviem, ale myslím si, že riešitelia KSP by nám s tým vedeli pomôcť.”.

“To je pravda. Zaujímalo by ma, či to zvládnu rýchlejšie ako my postavíme snehuliaka. Pozri, koľko snehu napadlo!”, povedal Zajo a išli spolu stavať snehuliaka.

Úloha

Mišov program dokáže generovať štvorcové obrázky, ktorých šírka (a tým pádom aj výška) je mocnina dvojky. Program postupuje takto:

1. Ak je strana štvorca \(1\), vyfarbi ho náhodne, buď celý na bielo, alebo celý na čierno
2. Inak:
   2.1. Rozdeľ štvorec na 4 menšie štvorce
   2.2. Náhodnú zo 4 štvrtín vyfarbi na bielo
   2.3. Náhodnú zo zvyšných troch štvrtín vyfarbi na čierno
   2.4. Pre zvyšné dve štvrtiny opakuj od kroku 1.

Podobnosť dvoch obrázkov definujeme ako veľkosť plochy, na ktorej majú oba obrázky rovnakú farbu. Napríklad nasledujúce dva obrázky majú podobnosť 8 (zhodujú sa v červeno orámovaných políčkach).

Na vstupe dostanete čierno-biely štvorcový obrázok. Zistite, aký najpodobnejší obrázok by dokázal Mišov postup vygenerovať (spomedzi všetkých takých, ktoré má šancu vygenerovať).

Formát vstupu

Na prvom riadku je čílo \(n\), \((1 \leq n \leq 512)\) – dĺžka strany štvorca. Číslo \(n\) je vždy mocnina čisla \(2\).

Nasleduje \(n\) riadkov po \(n\) čísel 0 alebo 1 (nie sú oddelené medzerami). Číslo 0 znamená bielu, 1 znamená čiernu farbu.

Formát výstupu

Na prvý riadok vypíšte, na koľkých miestach sa bude Mišov najpodobnejší obrázok odlišovať od toho na vstupe. Ďalej vypíšte najpodobnejší obrázok v rovnakom formáte ako obrázok na vstupe. Ak je viac možností, vypíšte ľubovolnú z nich.

Hodnotenie

Pre jednotlivé sady testovacích vstupov platia nasledovné obmedzenia:

Príklady

Input:

4
1001
0011
0111
1111

Output:

1
0001
0011
0111
1111

Input:

4
1010
0101
1010
0101

Output:

4
0011
0011
1010
0101

Tento vstup má viacero riešení.