#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5,INF=1e9;

int n,a[N];
long long pw[N];

struct abc{
	int x,y;
	long long pos;
	int val,num;
	abc(int X=0,int Y=0,long long Z=0,int W=INF){
		x=X,y=Y,pos=Z,val=W;
	}
};
bool operator <(abc X,abc Y){
	return X.x<Y.x;
}
void getmin(abc &X,abc Y){
	if(Y.val<X.val) X=Y;
}
vector <abc> P,Q;

void dfs1(int dep,int ed,int x,int y,int z,long long s){
	if(dep>ed){
		P.push_back((abc){y-x,z-y,s,z-x});
//		cout<<"P: "<<y-x<<" "<<z-y<<" "<<z-x<<endl;
		return ;
	}
	dfs1(dep+1,ed,x+a[dep],y,z,s);
	dfs1(dep+1,ed,x,y+a[dep],z,s+pw[dep]);
	dfs1(dep+1,ed,x,y,z+a[dep],s+2*pw[dep]);
}

void dfs2(int dep,int ed,int x,int y,int z,long long s){
	if(dep>ed){
		Q.push_back((abc){x-y,y-z,s,z-x});
//		cout<<"Q: "<<x-y<<" "<<y-z<<" "<<z-x<<endl;
		return ;
	}
	dfs2(dep+1,ed,x+a[dep],y,z,s);
	dfs2(dep+1,ed,x,y+a[dep],z,s+pw[dep]);
	dfs2(dep+1,ed,x,y,z+a[dep],s+2*pw[dep]);
}

abc c[N]; 
int lowbit(int x){
	return x & (-x);
}
void modify(int x,abc k){
	while(x<N) getmin(c[x],k),x+=lowbit(x);
}
abc query(int x){
	abc tot;
	while(x) getmin(tot,c[x]),x-=lowbit(x);
	return tot;
}

int v[N];

int main(){
	pw[0]=1;
	for(int i=1;i<=30;i++) pw[i]=pw[i-1]*3;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int m=n/2;
	dfs1(1,m,0,0,0,0);
	dfs2(m+1,n,0,0,0,0);
	
	sort(P.begin(),P.end());
	sort(Q.begin(),Q.end());
	
	int id=0;
	for(int i=0;i<P.size();i++) v[++id]=P[i].y;
	for(int i=0;i<Q.size();i++) v[++id]=Q[i].y;
	sort(v+1,v+id+1);
	int siz=unique(v+1,v+id+1)-v-1;
	for(int i=0;i<P.size();i++) P[i].num=lower_bound(v+1,v+siz+1,P[i].y)-v;
	for(int i=0;i<Q.size();i++) Q[i].num=lower_bound(v+1,v+siz+1,Q[i].y)-v;
	
	abc ans;
	int p=-1;
	for(int i=0;i<(int)P.size();i++){
		while(p+1<Q.size() && Q[p+1].x<=P[i].x) p++,modify(Q[p].num,Q[p]);
		
		abc tot=query(P[i].num);
		getmin(ans,(abc){0,0,P[i].pos+tot.pos,P[i].val+tot.val});
	}
	
//	for(int x=-B;x<=B;x++){
//		for(int y=-B;y<=x;y++){
//			for(int i=0;i<(int)P[x $].size();i++){
//				for(int j=0;j<(int)Q[y $].size();j++){
//					if(P[x $][i].x>=Q[y $][j].x)
//						getmin(ans,(abc){0,P[x $][i].pos+Q[y $][j].pos,P[x $][i].val+Q[y $][j].val});
//				}
//			}
//		}
//	}
	
	for(int i=1;i<=n;i++) cout<<ans.pos/pw[i]%3+1<<" ";
}