#include<bits/stdc++.h>
using namespace std;
constexpr int M=531442,inf=0x3f3f3f3f;
vector<tuple<int,int,int,int>>upd[M];
vector<tuple<int,int,int,int>>qry[M];
int n,m,na,nb,lim,ans=inf,ans1,ans2;
int N,num,sum,sum1[1<<13],sum2[1<<13],lsh[M],tr[M],tr1[M],tr2[M];
struct info{int x,y,z,sta1,sta2;
    info(int x_=0,int y_=0,int z_=0,int sta1_=0,int sta2_=0)
        {x=x_;y=y_;z=z_;sta1=sta1_;sta2=sta2_;}
}a[M],b[1594324];
void init1(){ lim=(1<<m)-1;
    auto insert=[&](auto x,auto y,auto sta1,auto sta2){
        a[++na]=info(x-y,x+y*2-sum,x*2+y,sta1,sta2);
    };
    for (int sta=1;sta<=lim;sta++){
        int low=sta&-sta;
        sum1[sta]=sum1[sta^low]+sum1[low];
    }
    for (int s=0;s<=lim;s++){
        int p=s^lim;insert(sum1[s],0,s,0);
        for (int t=p;t;(--t)&=p) insert(sum1[s],sum1[t],s,t);
    }
}
void init2(){ lim=(1<<n-m)-1;
    auto insert=[&](auto x,auto y,auto sta1,auto sta2){
        b[++nb]=info(y-x,-x-y*2,x*2+y-sum,sta1,sta2);
    };
    for (int sta=1;sta<=lim;sta++){
        int low=sta&-sta;
        sum2[sta]=sum2[sta^low]+sum2[low];
    }
    for (int s=0;s<=lim;s++){
        int p=s^lim;insert(sum2[s],0,s,0);
        for (int t=p;t;(--t)&=p) insert(sum2[s],sum2[t],s,t);
    }
}
void update(int x,int p,int sta1,int sta2){
    while (x<=num){ if (p<tr[x]) tr[x]=p,tr1[x]=sta1,tr2[x]=sta2; x+=x&-x; }
}
tuple<int,int,int> query(int x){
    int ans=inf,ans1,ans2; while (x){ if (tr[x]<ans) ans=tr[x],ans1=tr1[x],ans2=tr2[x]; x-=x&-x; } return make_tuple(ans,ans1,ans2);
}
void solve(){
    for (int i=1;i<=na;i++) lsh[++num]=a[i].x;
    sort(lsh+1,lsh+num+1);N=num=unique(lsh+1,lsh+num+1)-lsh-1;
    for (int i=1;i<=na;i++) a[i].x=lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh;
    for (int i=1;i<=nb;i++) b[i].x=lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh;
    num=0; for (int i=1;i<=na;i++) lsh[++num]=a[i].y;
    sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
    for (int i=1;i<=na;i++) a[i].y=lower_bound(lsh+1,lsh+num+1,a[i].y)-lsh;
    for (int i=1;i<=nb;i++) b[i].y=lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh;
    for (int i=1;i<=na;i++) qry[a[i].x].emplace_back(a[i].y,a[i].z,a[i].sta1,a[i].sta2);
    for (int i=1;i<=nb;i++) upd[b[i].x].emplace_back(b[i].y,b[i].z,b[i].sta1,b[i].sta2);
    for (int i=1;i<=num;i++) tr[i]=inf;
    for (int i=1;i<=N;i++){
        for (auto [x,p,sta1,sta2]:upd[i]) update(x,p,sta1,sta2);
        for (auto [x,p,sta1,sta2]:qry[i]){
            auto [tmp,tmp1,tmp2]=query(x);
            if (p+tmp<ans) ans=p+tmp,ans1=sta1|tmp1<<m,ans2=sta2|tmp2<<m;
        }
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;m=n>>1;
    for (int i=0;i<n;i++){
        int x;cin>>x;sum+=x;
        (i<m?sum1[1<<i]:sum2[1<<i-m])=x;
    }
    init1();init2();solve();
    for (int i=0;i<n;i++)
        printf("%d%c",ans1>>i&1?1:(ans2>>i&1?2:3)," \n"[i==n-1]);
    return 0;
}