ornament

Gigel vrea să confecţioneze un ornament pentru pomul de iarnă format din pătrăţele frumos colorate. Pătrăţelele pot arăta ca în desenul alăturat. Se observă faptul că ele pot avea $4$ culori diferite pe cele $4$ laturi, $3$, $2$ sau chiar o singură culoare pe toate cele $4$ laturi ale pătrăţelului.
Gigel are la dispoziţie $n$ ($n$ pătrat perfect) pătrăţele egale de acest tip cu laturile colorate doar în patru culori (alb, roşu, galben, albastru). Le vom numerota simplu de la $1$ la $4$.

Cerinţă

Să se scrie un program care primeşte o listă de $n$ pătrăţele colorate şi determină o aranjare a lor sub forma de pătrat de forma $k \times k\ (k \times k = n)$ astfel încât două laturi adiacente să aibă aceeaşi culoare, precum şi numărul de astfel de aranjări.

Date de intrare

Fişierul de intrare ornament.in va conţine pe prima linie valoarea $n$. Următoarele $n$ linii vor conţine câte patru numere naturale $N$, $E$, $S$, $V$ separate prin câte un spaţiu, reprezentând cele $4$ culori ale laturilor pătrăţelelor. Ordinea laturilor este considerată: Nord, Est, Sud, Vest şi pătrăţelele nu se vor roti. Ultima linie din fişierul de intrare va conţine una dintre valorile $1$ sau $2$; valoarea $1$ indică faptul că este cerută o soluţie corectă, iar valoarea $2$ indică faptul că este cerut numărul de soluţii corecte.

Date de ieşire

În cazul cerinţei $1$ fişierul de ieşire ornament.out va conţine $k$ linii. Fiecare linie va conţine câte $k$ valori reprezentând numerele de ordine ale pătrăţelelor din fişierul de intrare, aranjate astfel încât să fie respectată condiţia din enunţ. În cazul cerinţei $2$, fişierul de ieşire va conţine pe prima linie un singur număr natural reprezentând numărul de soluţii corecte.

Restricţii

• $n = 4, 9, 16$
• Pentru datele de intrare problema are întotdeauna soluţie, în timpul indicat.

Exemplul 1

ornament.in

16
4 4 1 1
4 3 1 2
2 2 2 3
4 1 3 2
1 1 3 1
1 3 1 1
2 4 1 3
3 1 1 4
3 2 4 1
1 3 2 2
1 4 4 3
1 1 2 4
4 3 3 2
2 1 1 3
4 4 3 1
2 4 4 4
1

ornament.out

2 3 4 9
10 7 8 1
16 12 6 11
13 14 5 15

Explicație

Soluţia corespunde aranjării

|-4-| |-2-| |-4-| |-3-|
2   3 3   2 2   1 1   2
|-1-| |-2-| |-3-| |-4-|
|-1-| |-2-| |-3-| |-4-|
2   3 3   4 4   1 1   4
|-2-| |-1-| |-1-| |-1-|
|-2-| |-1-| |-1-| |-1-|
4   4 4   1 1   3 3   4
|-4-| |-2-| |-1-| |-4-|
|-4-| |-2-| |-1-| |-4-|
2   3 3   1 1   1 1   4
|-3-| |-1-| |-3-| |-3-|

Exemplul 2

ornament.in

16
4 4 1 1
4 3 1 2
2 2 2 3
4 1 3 2
1 1 3 1
1 3 1 1
2 4 1 3
3 1 1 4
3 2 4 1
1 3 2 2
1 4 4 3
1 1 2 4
4 3 3 2
2 1 1 3
4 4 3 1
2 4 4 4
2

ornament.out

1