#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

// const int K = 1 << 15;
// int cnt[K];

// void reset() {
//     for (int i = 0; i < K; ++i) cnt[i] = 0;
// }

// vi bucket_sort(vi &A) {
//     int n = A.size();
//     vi ans(n);

//     reset();
//     for (int x : A) cnt[x | (K - 1)]++;
//     for (int i = 1; i < K; ++i) cnt[i] += cnt[i - 1];
    
//     reset();
//     for (int x : A) cnt[x >> 15]++;
//     for (int i = 1; i < K; ++i) cnt[i] += cnt[i - 1];

// }

vi sort(vi &A) {
    int n = A.size();
    vector<int> cnt(25 + 1, 0);
    for (int x : A) cnt[x]++;
    for (int i = 1; i <= 25; ++i) cnt[i] += cnt[i - 1];
    vi ans(n);
    for (int i = n - 1; i >= 0; --i) {
        ans[--cnt[A[i]]] = i;
    }
    return ans;
}

vi solve(vi A) {
    int n = A.size();
    for (int &x : A) x = __builtin_ctz(x);
    vi p = sort(A);   
    if (n % 2 == 1) {
        vi ans(n);
        for (int i = 0; i < n; i += 2)
            ans[i / 2] = p[i];
        for (int i = 1; i < n; i += 2)
            ans[(n + i) / 2] = p[i];
        return ans;
    } else {
        vi ans(n);
        for (int i = 1; i < n; i += 2)
            ans[i / 2] = p[i];
        for (int i = 0; i < n; i += 2)
            ans[(i + n) / 2] = p[i];
        return ans;
    }
}