#include <bits/stdc++.h>


using namespace std;
const int maxn = 1000025;
const int inf = 1e9;

struct Item {
    int d1, d2, d3;
    int mx, my, mz;
    Item (int _d1, int _d2, int _d3, int _mx, int _my, int _mz)
        : d1(_d1), d2(_d2), d3(_d3), mx(_mx), my(_my), mz(_mz) {}
    friend bool operator<(const Item &lhs, const Item &rhs) {
        return lhs.d1 < rhs.d1;
    }
};

template <typename T>
struct Fenwick {
    T def;
    const vector<int> & u;
    vector<T> mn;
    Fenwick(const vector<int> &_u, T _def)
        : u(_u), def(_def), mn(u.size()+1, def) {}
    void add(int p, T t) {
        p = lower_bound(u.begin(), u.end(), p) - u.begin();
        for (++p; p < mn.size(); p += p & -p)
            mn[p] = min(mn[p], t);
    }
    T query(int p) {
        p = lower_bound(u.begin(), u.end(), p) - u.begin();
        T res = def;
        for (++p; p > 0; p -= p & -p)
            res = min(res, mn[p]);
        return res;
    }
};

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> org_a(n);
    for (int i = 0; i < n; i++)
        cin >> org_a[i];

    int a = n/2, b = n-a;
    vector<int> A(a), B(b);
    for (int i = 0; i < n; i++)
        if (i < a)
            A[i] = org_a[i];
        else
            B[i-a] = org_a[i];
    auto Enum = [](const vector<int> &vec) {
        int n = vec.size();
        vector<int> sum(1 << n);
        for (int i = 0; i < n; i++)
            sum[1 << i] = vec[i];
        for (int i = 0; i < (1<<n); i++)
            sum[i] = sum[i - (i & -i)] + sum[i & -i];
        vector<Item> res;
        const int U = (1<<n)-1;
        for (int s = 0; s < (1<<n); s++) {
            int u = ~s & U;
            for (int f = u; ; f = (f - 1) & u) {
                int x = sum[s];
                int y = sum[u ^ f];
                int z = sum[f];
                res.emplace_back(x - y, y - z, x - z, s, u ^ f, f);
                if (!f)
                    break;
            }
        }
        return res;
    };
    auto ea = Enum(A);
    auto eb = Enum(B);
    sort(ea.begin(), ea.end());
    sort(eb.begin(), eb.end());
    reverse(eb.begin(), eb.end());
    vector<int> u;
    for (int i = 0; i < (int)ea.size(); i++) {
        u.push_back(ea[i].d2);
    }
    for (int i = 0; i < (int)eb.size(); i++) {
        u.push_back(-eb[i].d2);
    }
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    Fenwick<tuple<int,int,int,int>> BIT(u, make_tuple(inf, inf, inf, inf));
    int ans = 1e9;
    int anx, any, anz;
    for (int i = 0, j = 0; i < (int)ea.size(); i++) {
        while (j < (int)eb.size() && ea[i].d1 + eb[j].d1 >= 0) {
            BIT.add(-eb[j].d2,
                    make_tuple(eb[j].d3, eb[j].mx, eb[j].my, eb[j].mz));
            j++;
        }
        // a + b >= 0
        // -b <= a
        auto [cost, mx, my, mz] = BIT.query(ea[i].d2);
        if (cost == inf)
            continue;
        cost += ea[i].d3;
        mx = (mx << a) | ea[i].mx;
        my = (my << a) | ea[i].my;
        mz = (mz << a) | ea[i].mz;
        if (cost < ans) {
            ans = cost;
            anx = mx;
            any = my;
            anz = mz;
        }
    }
    // cerr << bitset<30>(anx) << endl;
    // cerr << bitset<30>(any) << endl;
    // cerr << bitset<30>(anz) << endl;
    for (int i = 0; i < n; i++) {
        if (anx >> i & 1)
            cout << 1;
        else if (any >> i & 1)
            cout << 2;
        else
            cout << 3;
        cout << (i+1==n ? '\n' : ' ');
    }
}