#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const mod=1000000007;
ll const md=998244353;
ll mypowr(ll a,ll b) {ll res=1;a%=mod; assert(b>=0);
for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll mypow(ll a,ll b) {ll res=1;assert(b>=0);
for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
ifstream in("elevi.in");
ofstream out("elevi.out");
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
vector<int> v[1005];
int f[1005];
ll dp[1005];
int p(ll x){
if(x<=1)return 0;
if(x<=3)return 1;
if(x%2==0||x%3==0)return 0;
for(ll i=5;i*i<=x;i+=6){
if(x%i==0||x%(i+2)==0)return 0;
}
return 1;
}
int main()
{
ios_base::sync_with_stdio(0);
cout<<fixed<<setprecision(15);
cin.tie(0);cout.tie(0);
ll n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>f[i];
}
ll mx2=0,pos2=0;
for(int i=1;i<=n;++i){
v[i].pb(f[i]);
int mx=0,pos=0;
for(int j=i-1;j>=1;--j){
if(f[i]>f[j]){
if(dp[j]>mx){
mx=dp[j];
pos=j;
}
}
}
dp[i]=mx+1;
if(pos>0){
for(auto u:v[pos]){
v[i].pb(u);
}
}
if(dp[i]>mx2){
mx2=dp[i];
pos2=i;
}
}
sort(v[pos2].begin(),v[pos2].end());
for(auto u:v[pos2]){
cout<<u<<" ";
}
cout<<'\n';
for(int i=1;i<=n;++i){
if(p(f[i])){
cout<<f[i]<<" ";
}
}
return 0;
}
