Као што се иначе често дешава у такмичарским задацима, нашли сте се у чудној ситуацији: дато вам је \(N\) гомила новчића (\(i\)-та гомила садржи \(A_i\) новчића). Планирате да организујете \(N\) такмичења, где ћете за свако од њих искористити једну гомилу као наградни фонд (\(A_1\) за прво, \(A_2\) за друго, и тако даље).

За свако такмичење треба да одаберете колико ће учесника бити награђено (обележићемо број награђених на \(i\)-том такмичењу са \(B_i\)). Све награде на једном такмичењу су исте, тако да \(A_i\) мора бити дељиво са \(B_i\). Додатно, све вредности \(B_i\) морају бити прости бројеви (нисте сигурни зашто, али неко вам је рекао да је то добра идеја).

Да би циклус такмичења био интересантнији, планирате да одаберете вредности \(B_i\) тако да су награде на свим такмичењима различите, тј. да за сваки пар вредности \((i,j)\) важи \(\frac{A_i}{B_i} \neq \frac{A_j}{B_j}\). Ваш задатак је да напишете програм који ће пронаћи овакву поделу или утврдити да то није могуће.

Опис улаза

У првом реду стандардног улаза налази се један цео број \(N\) – број такмичења која организујете. У другом реду налази се \(N\) бројева \(A_1, A_2, \ldots, A_N\), који представљају број новчића у наградним фондовима појединачних такмичења.

Опис излаза

У првом и једином реду стандардног излаза исписати \(N\) бројева \(B_1, B_2, \ldots, B_N\) – број награђених такмичара на сваком такмичењу, тако да су услови из текста задатка задовољени. Уколико то није могуће, исписати -1.

Уколико постоји више решења, исписати било које.

Пример 1

Улаз

4
10 8 15 7

Излаз

2 2 5 7

Пример 2

Улаз

2
2 7

Излаз

-1

Објашњење примера

У првом примеру, једно могуће решење је да се на првом такмичењу доделе две награде од по \(5\) новчића, на другом две од по \(4\), на трећем пет од по \(3\) и на четвртом седам награда од по једног новчића. Пошто су све награде различите, и на сваком такмичењу је награђен прост број такмичара, ова подела задовољава дате услове. Могућа су и друга решења, на пример да се на првом такмичењу награди пет, а на трећем три такмичара.

У другом примеру, једино решење где је награђен прост број такмичара је 2 7 (јер \(1\) није прост број). Како су на њему награде на оба такмичења исте (по један новчић), оно не задовољава све услове, тако да не постоји решење.

Ограничења

• \(1 \leq N\)
• \(1 \leq A_i\)

Тест примери су подељени у три дисјунктне групе: * У тест примерима који вреде \(20\) поена важи \(N \leq 8, A_i \leq 1000\) * У тест примерима који вреде \(20\) поена важи \(N \leq 1000, A_i \leq 3000\) * У тест примерима који вреде \(60\) поена важи \(N \leq 1000, A_i \leq 200000\)