Yet Another Problem on GCD

0

0 votes
Medium
Problem

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=2j=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

1m200000

1Ai100000000

Output Format

Print just one line containing m integers in the order described.

Time Limit: 2.5
Memory Limit: 256
Source Limit:
Editor Image

?