acoperire

Dintr-o suprafaţă pătrată cu latura de $N$ unităţi care este formată din $N \cdot N$ pătrăţele cu latura de o unitate se decupează cele $4$ pătrăţele din colţuri.

Cerința

Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie $4$ unităţi care au forma următoare:

Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele $8$ moduri de a le aşeza.

Date de intrare

Fișierul de intrare acoperire.in conține pe prima linie un număr natural $N$, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire acoperire.out va conține valoarea $-1$ pe prima linie dacă problema nu are soluţie, iar în caz contrar va avea următoarea structură: $N$ linii cu câte $N$ valori fiecare reprezentând codificarea suprafeţei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu. Poziţiile ocupate de prima piesă aşezată se vor codifica cu $1$, poziţiile ocupate de a doua piesă aşezată se vor codifica cu $2$ etc. Corespunzător colţurilor lipsă se va scrie valoarea $0$.

Restricții și precizări

• $6 \leq n \leq 200$
• Piesele trebuie să fie complet în interiorul zonei;
• Zona trebuie acoperită integral;
• Două piese nu se pot suprapune complet sau parţial;

Exemplu

acoperire.in

6

acoperire.out

0 7 2 2 2 0 
3 7 2 4 4 4 
3 7 7 4 5 5 
3 3 6 1 1 5 
6 6 6 8 1 5 
0 8 8 8 1 0