Cerința

Marian a fost foarte interesat de metoda divide et impera și a primit de la profesorul său o problemă: se dă o matrice de dimensiune 2n și ea trebuie parcursă după o anumită regulă bazată pe divide et impera. Pe baza a trei exemple, el trebuie să descopere regula și s-o aplice . Din păcate, acesta nu reusește și vă cere ajutorul. Vrea o rezolvare foarte eficienta atât din punct de vedere al timpului de execuție cât și a limitei de memorie.

Date de intrare

Fișierul de intrare matrice_div_et_imp.in conține pe prima linie numărul n, iar pe celelalte 2n linii câte 2n numere naturale nenule separate prin spații.

Date de ieșire

Fișierul de ieșire matrice_div_et_imp.out va conține o linie cu cele 2n*2n numere ale matricei , parcurse după respectiva regulă.

Restricții și precizări

• 0 ≤ n ≤ 9
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplu 1:

matrice_div_et_imp.in

1
1 2 
3 4

matrice_div_et_imp.out

1 4 2 3 

Exemplu 2:

matrice_div_et_imp.in

2
15 12 13 14
36 56 34 58
98 80 79 11
10 43 47 50

matrice_div_et_imp.out

15 56 12 36 79 50 11 47 13 58 14 34 98 43 80 10 

Exemplu 3:

matrice_div_et_imp.in

3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

matrice_div_et_imp.out

1 10 2 9 19 28 20 27 3 12 4 11 17 26 18 25 37 46 38 45 55 64 56 63 39 48 40 47 53 62 54 61 5 14 6 13 23 32 24 31 7 16 8 15 21 30 22 29 33 42 34 41 51 60 52 59 35 44 36 43 49 58 50 57 

Observație pentru ultimul exemplu: toate numerele sunt pe o singură linie