sablon

Gigel şi Vasilică imaginează un mod de a transmite mesaje pe care nimeni să nu le poată descifra. Mesajul este ascuns într-un text care are $N$ linii şi pe fiecare linie sunt exact $N$ caractere – litere mari ale alfabetului englez, cifre, semne de punctuaţie şi caracterul spaţiu.

Decodificarea se face cu ajutorul unui şablon, de aceleaşi dimensiuni ca şi textul, care are câteva găuri. Suprapunând şablonul peste text rămân vizibile câteva caractere. Acestea se citesc în ordinea liniilor, de sus în jos, iar pe aceeaşi linie de la stânga la dreapta. Apoi hârtia cu textul se roteşte spre stânga, în sens trigonometric, cu ${90\degree}$, şablonul rămânând fix. Alte caractere devin vizibile şi acestea se citesc în acelaşi mod. Operaţia se repetă de încă două ori (rotire cu ${180\degree}$, respectiv cu ${270\degree}$), până când textul ajunge, printr-o nouă rotaţie cu ${90\degree}$, din nou în poziţia iniţială.

Din păcate, şablonul pentru codificare/decodificare s-a pierdut. În schimb a rămas la Gigel mesajul iniţial iar la Vasilică a ajuns textul care conţine mesajul.

Cerință

Să se reconstituie şablonul care a fost folosit la codificare.

Date de intrare

Fişierul de intrare sablon.in conţine pe prima linie, mesajul iniţial. Pe linia a doua a fişierului de intrare se găseşte valoarea $N$.

Următoarele $N$ linii conţin textul care ascunde mesajul.

Date de ieșire

Fişierul de ieşire sablon.out conţine $N$ linii a câte $N$ caractere. Caracterele sunt O (pentru reprezentarea unei găuri) şi X.

Restricții și precizări

• prin rotirea textului nici una din găuri nu se va suprapune peste nici una din poziţiile ocupate de o gaură în poziţiile precedente ale textului
• $1 \leq N \leq 50$
• mesajul are maxim $1 \ 000$ caractere şi se încheie cu un caracter diferit de spaţiu
• în cazul în care există mai multe soluţii, afişaţi una dintre ele

Exemplu

sablon.in

CODIFICARE CU SABLON
10
ABCDCEFAGH
IJOKLEMNOP
DQRSTUVWCX
YZAIBCRDEF
GFHIJKLMNI
AJKLMNOPSQ
RSTOUV WXY
ZBABCDEFGU
HIJKNLMCNO
PQLRS TUVW

sablon.out

XXXXOXXXXX
XXOXXXXXXX
OXXXXXXXXX
XXXOXXXXXX
XOXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX