Untitled

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

using namespace std;
const int M = 1e5 + 10;
int n, ind;
int a[M];
bool mark[M * 2 + 5000];
vector <int> adj[M * 2 + 5000];
map <int, int> mapp;
vector <int> prime;
vector <int> vecind;
vector <int> vec;
int ans[M];

void fp(){
	int z = 32000;
	bool vis[z] = {};
	for(int i = 2; i < z; i++){
		if(!vis[i]){
			prime.pb(i);
			for(int j = i; j < z; j += i)
				vis[j] = 1;
		}
	}
}

inline void add_edge(int i, int j){
	int r, x;
	x = mapp[j];
	if(x == 0){
		mapp[j] = ind;
		x = ind;
		ind++;
	}
	adj[i].pb(x);
	adj[x].pb(i);
}
void analize(int i){
	int b = a[i];
	for(ll j : prime){
		if(j * j > b)
			break;
		if(!(b % j))
			add_edge(i, j);
		while(!(b % j))
			b /= j;
		if(b == 1)
			break;
	}
	if(b != 1)
		add_edge(i, b);
}

void dfs(int v){
	if(v < n){
		vecind.pb(v);
		vec.pb(a[v]);
	}
	mark[v] = 1;
	for(int u : adj[v]){
		if(!mark[u])
			dfs(u);
	}
}
void prs(){
	sort(vec.begin(), vec.end());
	sort(vecind.begin(), vecind.end());
	for(int i = 0; i < vec.size(); i++)
		ans[vecind[i]] = vec[i];
	vecind.clear();
	vec.clear();
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	fp();
	cin >> n;
	ind = n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		analize(i);
	}


	for(int i = 0; i < n; i++){
		if(mark[i] == 0){
			dfs(i);
			prs();
		}
	}
	for(int i = 0; i < n; i++)
		cout << ans[i] << ' ';
	return 0;
}