首先可以看出不互质的两数在序列中的相对位置不会改变，然后就想到在不互质的数之间建边，然后尝试去选数。

然后从这里就开始离谱了，我的想法是直接把图拆分成若干，于是就按权值从小到大考虑每个点，如果还没有被选到某条链上，就从它开始，贪心的走邻接的最小点dfs找出一条链，然后放到生成的序列最后，直到所有点都被选到。这样是Alice的操作，然后Bob的操作就一个一个数考虑，贪心的往前能换且换了字典序更大就换，类似冒泡的一个过程，我不知道有什么正确性，纯粹考场上骗分编出来的。

代码如下

#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i) 
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;

const int maxn=2e3+10;

int n;int a[maxn];
vector<int>vec;

struct Graph{
	vector<int>E[maxn];
	void lqx(int u,int v){ E[u].emplace_back(v); }
	bool vis[maxn];
	void Dfs(int u){
		vis[u]=true;vec.emplace_back(a[u]);
		for(auto v : E[u])if(!vis[v])Dfs(v);
	}
}G;

void solve(){
	cin>>n;Rep(i,1,n)cin>>a[i];
	sort(a+1,a+n+1);
    Rep(i,1,n)Rep(j,1,n)if(i!=j && __gcd(a[i],a[j])!=1)G.lqx(i,j);
	vec.emplace_back(0);Rep(i,1,n)if(!G.vis[i])G.Dfs(i);
	Rep(i,1,n){
		int pos=0;
		Dwn(j,i-1,1){
			if(__gcd(vec[j],vec[i])!=1)break;
			if(vec[j]<vec[i])pos=j;
		}
		if(pos){
			int j=i;while(j>pos){ swap(vec[j],vec[j-1]);--j; }
		}
	}
	Rep(i,1,n)cout<<vec[i]<<" ";
}

int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }