Game of Life

Az élet szép, ám éppúgy megjelennek benne szomorú események, mint ahogy örömteliek is. Sajnos az emberiség jelentős része önző és hajlamos elfelejteni, hogy rajtunk kívül élnek más létformák is bolygónkon. Így e feladatban, mintegy emlékeztetőül iciri-piciri sejtek életét kell nyomon követnünk.
A sejtek egy négyzetrácsos Petri-csészében éldegélnek, melynek mindegyik cellája, vagy üres, vagy élő sejtet tartalmaz. Az üres cellák az o karakterrel, az élő sejtet tartalmazó cellák az x karakterrel vannak szimbolizálva. A feladat, hogy egy kezdeti állapot ismeretében kiírjuk, hogy n iterációt követően, hogy fog kinézni a Petri-csésze állapota.
Az egyes iterációk az alábbi szabályok szerint alakulnak:

• minden újabb iteráció a jelenlegi (pillanatnyi) állapot alapján alakul ki egyetlen pillanat alatt
• minden sejt aminek közvetlen környezetében (tőle 1 egységre) kevesebb mint 2 sejt található meghal, így a következő iterációban az ő cellája üres lesz
• ha egy sejt közvetlen környezetében (tőle 1 egységre) 2-3 sejt tartózkodik, akkor az a sejt életben marad
• ha egy sejt közvetlen környezetében (tőle 1 egységre) 3-nál több sejt tartózkodik akkor túlnépesedés miatt meghal
• ha egy üres cella közvetlen környezetében (tőle 1 egységre) pontosan 3 sejt van akkor a következő iterációban a cellában megjelenik egy sejt

Input

A bemenet 3 egységből áll:

• Az első sorban egy pozitív egész n szám található ami a négyzetes tábla oldalhosszát adja meg. A tábla bal felső koordinátája a (0,0) pont és jobbra, illetve lefelé egyesével nő az indexelés.
• A következő sorban a végrehajtandó I iterációk száma szerepel nemnegatív egészként. A start iteráció a 0.-nak tekintendő.
• A következő n sor mindegyike egy n hosszú stringet tartalmaz, mely a Petri-csésze kezdeti állapotát írja le. A stringben csak az o és x karakterek szerepelnek szeparátor nélkül.

Output

Az output n darab n hosszú string, mely I iteráció elteltével a Petri-csésze állapotát tükrözi a megadott szabályok alapján.

Megkötések

Példa