#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
using namespace std;

int countEven(long long n) {
    int c = 0;
    while (n != 0) {
        int digit = n % 10;
        if (digit % 2 == 0) {
            c++;
        }
        n = n / 10;
    }
    return c;
}

int countOdd(long long n) {
    int c = 0;
    while (n != 0) {
        int digit = n % 10;
        if (digit % 2 != 0) {
            c++;
        }
        n = n / 10;
    }
    return c;
}



int main() {

    int n;cin >> n;
    vector<int> v1, v2;

    for (int i = 0;i < n;i++) {
        int value;cin >> value;
        v1.push_back(value);
        v2.push_back(value);
    }

    sort(v1.begin(), v1.end(), [](int a, int b) {
        int ca = countEven(a);
        int cb = countEven(b);

        if (ca != cb) {
            return ca < cb;
        }
        else {
            return a < b;
        }
    });

    for (auto value : v1) {
        cout << value << " ";
    }

    cout << endl;
    stable_sort(v2.begin(), v2.end(), [](int a, int b) {
        int ca = countOdd(a);
        int cb = countOdd(b);

        return ca < cb;

    });

    for (auto value : v2) {
        cout << value << " ";
    }
    return 0;
}

