Problem description

Janek, będąc bardzo zajęty treningiem do olimpiady, nie zauważył, że święta już dawno minęły. Pomimo to zdecydował się napisać jeszcze list do Świętego Mikołaja z prośbą o zaległy prezent. Janek, podobnie jak rok wcześniej, poprosi o permutację n liczb, jednak chce, żeby była jak najmniej podobna do tej, którą dostał rok wcześniej. W tym celu zdefiniował współczynnik podobieństwa dwóch permutacji p i q jako ∑_inwd(p_i,q_i), gdzie nwd(x,y) oznacza największy wspólny dzielnik liczb x i y. Janek chce poprosić o taką permutację q, która zminimalizuje współczynnik podobieństwa z permutacją p, którą dostał w tamtym roku. Ponieważ Janek jest bardzo zajęty implementowaniem zadania z geometrii na następne kółko, prosi Cię o pomoc w znalezieniu dowolnej takiej permutacji.

Wejście

W pierwszym wierszu znajduje się n, długość permutacji.
W drugim wierszu n liczb p₁, p₂, …, p_n, oznaczających permutację p.

Wyjście

W pierwszym i jedynym wierszu wypisz n różnych liczb q₁, q₂, …, q_n, czyli permutację q mającą minimalny współczynnik podobieństwa z p. Jeśli jest więcej niż jedna taka permutacja, możesz wypisać dowolną.

Ograniczenia

1 ≤ n_i ≤ 2 ⋅ 10⁵
1 ≤ p_i ≤ n, p_i ≠ p_j dla 1 ≤ i ≠ j ≤ n

Przykład

3
2 1 3

1 3 2

7
3 1 7 4 2 5 6

4 3 6 7 5 2 1