Matrix

Time limit: 1s Memory limit: 64MB Input: matrix.in Output: matrix.out

Cerință

Andreea a primit o temă de la profesoara de matematică să completeze un tabel, cunoscând un șir AA format din NN numere întregi. Tabelul este o matrice pătratică de mărime NNN \cdot N. Fiecare celulă din matrice de forma {i,j}\{ i,j \} va avea valoarea: gcd(Ai,Aj)(A_i,A_j).

Andreea a completat tabelul și s-a pus să se culce. Din păcate, fratele ei mai mic Răzvan a observat tabelul și șirul pe birou, iar din plictiseală, a aruncat șirul la gunoi, iar valorile din tabel le-a rearanjat într-o ordine random.

Când s-a trezit, Andreea a încremenit când și-a văzut tabelul modificat. S-ar fi apucat din nou să-l refacă, doar că nu și-a mai găsit șirul cu valorile date de profesoară.

Cum aceasta este în criză de timp și există posibilitatea să fie mai multe șiruri valide, aceasta vă roagă să-i aflați un șir care să construiască toate numerele din tabel.

Ordinea numerelor din noul tabel nu contează, astfel le putem rearanja cum dorim noi.

Date de intrare

Pe prima linie din fișierul de intrare matrix.in se va găsi un singur număr natural NN, cu semnificația din enunț.
Pe a doua linie se vor găsi cele NNN \cdot N numere naturale, acestea fiind valorile din matricea amestecată de Răzvan.

Date de ieșire

Pe prima linie a fișierului de ieșire matrix.out se va găsi șirul găsit de voi.

Restricții și precizări

  • 1N5001 \leq N \leq 500;
  • Valorile din matricea amestecată de Bob sunt numere naturale nenule 109\leq 10^9.
  • Dacă există mai multe soluții posibile, vă este permis să afișați oricare dintre ele.

Exemplul 1

matrix.in

4
14 1 11 14 10 14 2 1 1 2 2 14 2 1 1 1 

matrix.out

10 11 14 14 

Exemplul 2

matrix.in

1
6

matrix.out

6

Log in or sign up to be able to send submissions!