Pratik : I can code QuickSort, MergeSort, HeapSort... all blindfolded.
Abhinandan : Yeah, that's all cool and stuff... BUT CAN YOU SORT THESE???!!
The function F is defined as -
F(n)=∑i=ni=2∑j=nj=1j[gcd(j,n)=i]
value of [P] is 1 if P is true otherwise 0.
Oh no!! Pratik is not intelligent. So he asks you to solve this.
You are given m positive integers. You need to sort these according to increasing order of their respective images under F. If two integers have the same image under F, their relative order in the input list should be retained.
Input Format
The input consists of two lines. The first line contains a positive integer m. The second line contains m space separated integers, Ai (i=1..m).
Constraints
1≤m≤200000
1≤Ai≤100000000
Output Format
Print just one line containing m integers in the order described.