There are N integers written on a blackboard. The i-th integer is A_i.

Takahashi and Aoki will arrange these integers in a row, as follows:

* First, Takahashi will arrange the integers as he wishes.
* Then, Aoki will repeatedly swap two adjacent integers that are coprime, as many times as he wishes.



We will assume that Takahashi acts optimally so that the eventual sequence will be lexicographically as small as possible, and we will also assume that Aoki acts optimally so that the eventual sequence will be lexicographically as large as possible. Find the eventual sequence that will be produced.

Constraints

* 1 ≦ N ≦ 2000
* 1 ≦ A_i ≦ 10^8

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 … A_N


Output

Print the eventual sequence that will be produced, in a line.

Examples

Input

5
1 2 3 4 5


Output

5 3 2 4 1


Input

4
2 3 4 6


Output

2 4 6 3
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define rs (x<<1|1)
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) (int((x).size()))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
const int maxn=2e3+5;
int n;
int a[maxn],vis[maxn],dep[maxn];
vector<int>e[maxn];
priority_queue<int>A;
int getgcd(int x,int y){
	return !x?y:getgcd(y%x,x);
}
void dfs(int x){
	rep2(i,0,SZ(e[x]))if(!dep[e[x][i]])dep[e[x][i]]=dep[x]+1,dfs(e[x][i]);
}
int main(){
	read(n);
	rep(i,1,n)read(a[i]);
	sort(a+1,a+n+1);
	rep(i,1,n)rep(j,i+1,n)if(getgcd(a[i],a[j])!=1)e[i].pb(j),e[j].pb(i);
	rep(i,1,n)if(!dep[i])dep[i]=1,dfs(i),A.push(i);
	rep(i,1,n){
		int x=A.top();A.pop();
		printf("%d ",a[x]);
		rep2(i,0,SZ(e[x]))if(dep[e[x][i]]==dep[x]+1)A.push(e[x][i]);
	}
	return 0;
}