Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Као што се иначе често дешава у такмичарским задацима, нашли сте се у чудној ситуацији: дато вам је \(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\) није прост број). Како су на њему награде на оба такмичења исте (по један новчић), оно не задовољава све услове, тако да не постоји решење.

Ограничења

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