Kao što se inače često dešava u takmičarskim zadacima, našli ste se u čudnoj situaciji: dato vam je ~N~ gomila novčića (~i~-ta gomila sadrži ~A_i~ novčića). Planirate da organizujete ~N~ takmičenja, gde ćete za svako od njih iskoristiti jednu gomilu kao nagradni fond (~A_1~ za prvo, ~A_2~ za drugo, i tako dalje).

Za svako takmičenje treba da odaberete koliko će učesnika biti nagrađeno (obeležićemo broj nagrađenih na ~i~-tom takmičenju sa ~B_i~). Sve nagrade na jednom takmičenju su iste, tako da ~A_i~ mora biti deljivo sa ~B_i~. Dodatno, sve vrednosti ~B_i~ moraju biti prosti brojevi (niste sigurni zašto, ali neko vam je rekao da je to dobra ideja).

Da bi ciklus takmičenja bio interesantniji, planirate da odaberete vrednosti ~B_i~ tako da su nagrade na svim takmičenjima različite, tj. da za svaki par vrednosti ~(i,j)~ važi ~\frac{A_i}{B_i} \neq \frac{A_j}{B_j}~. Vaš zadatak je da napišete program koji će pronaći ovakvu podelu ili utvrditi da to nije moguće.

Opis ulaza

U prvom redu standardnog ulaza nalazi se jedan ceo broj ~N~ -- broj takmičenja koja organizujete. U drugom redu nalazi se ~N~ brojeva ~A_1, A_2, \ldots, A_N~, koji predstavljaju broj novčića u nagradnim fondovima pojedinačnih takmičenja.

Opis izlaza

U prvom i jedinom redu standardnog izlaza ispisati ~N~ brojeva ~B_1, B_2, \ldots, B_N~ -- broj nagrađenih takmičara na svakom takmičenju, tako da su uslovi iz teksta zadatka zadovoljeni. Ukoliko to nije moguće, ispisati -1.

Ukoliko postoji više rešenja, ispisati bilo koje.

Primer 1

Ulaz

4
10 8 15 7

Izlaz

2 2 5 7

Primer 2

Ulaz

2
2 7

Izlaz

-1

Objašnjenje primera

U prvom primeru, jedno moguće rešenje je da se na prvom takmičenju dodele dve nagrade od po ~5~ novčića, na drugom dve od po ~4~, na trećem pet od po ~3~ i na četvrtom sedam nagrada od po jednog novčića. Pošto su sve nagrade različite, i na svakom takmičenju je nagrađen prost broj takmičara, ova podela zadovoljava date uslove. Moguća su i druga rešenja, na primer da se na prvom takmičenju nagradi pet, a na trećem tri takmičara.

U drugom primeru, jedino rešenje gde je nagrađen prost broj takmičara je 2 7 (jer ~1~ nije prost broj). Kako su na njemu nagrade na oba takmičenja iste (po jedan novčić), ono ne zadovoljava sve uslove, tako da ne postoji rešenje.

Ograničenja

• ~1 \leq N~
• ~1 \leq A_i~

Test primeri su podeljeni u tri disjunktne grupe:

• U test primerima koji vrede ~20~ poena važi ~N \leq 8, A_i \leq 1000~
• U test primerima koji vrede ~20~ poena važi ~N \leq 1000, A_i \leq 3000~
• U test primerima koji vrede ~60~ poena važi ~N \leq 1000, A_i \leq 200000~