#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8Y2xpbWl0cz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBjb3VudEV2ZW4obG9uZyBsb25nIG4pIHsKICAgIGludCBjID0gMDsKICAgIHdoaWxlIChuICE9IDApIHsKICAgICAgICBpbnQgZGlnaXQgPSBuICUgMTA7CiAgICAgICAgaWYgKGRpZ2l0ICUgMiA9PSAwKSB7CiAgICAgICAgICAgIGMrKzsKICAgICAgICB9CiAgICAgICAgbiA9IG4gLyAxMDsKICAgIH0KICAgIHJldHVybiBjOwp9CgppbnQgY291bnRPZGQobG9uZyBsb25nIG4pIHsKICAgIGludCBjID0gMDsKICAgIHdoaWxlIChuICE9IDApIHsKICAgICAgICBpbnQgZGlnaXQgPSBuICUgMTA7CiAgICAgICAgaWYgKGRpZ2l0ICUgMiAhPSAwKSB7CiAgICAgICAgICAgIGMrKzsKICAgICAgICB9CiAgICAgICAgbiA9IG4gLyAxMDsKICAgIH0KICAgIHJldHVybiBjOwp9CgoKCmludCBtYWluKCkgewoKICAgIGludCBuO2NpbiA+PiBuOwogICAgdmVjdG9yPGludD4gdjEsIHYyOwoKICAgIGZvciAoaW50IGkgPSAwO2kgPCBuO2krKykgewogICAgICAgIGludCB2YWx1ZTtjaW4gPj4gdmFsdWU7CiAgICAgICAgdjEucHVzaF9iYWNrKHZhbHVlKTsKICAgICAgICB2Mi5wdXNoX2JhY2sodmFsdWUpOwogICAgfQoKICAgIHNvcnQodjEuYmVnaW4oKSwgdjEuZW5kKCksIFtdKGludCBhLCBpbnQgYikgewogICAgICAgIGludCBjYSA9IGNvdW50RXZlbihhKTsKICAgICAgICBpbnQgY2IgPSBjb3VudEV2ZW4oYik7CgogICAgICAgIGlmIChjYSAhPSBjYikgewogICAgICAgICAgICByZXR1cm4gY2EgPCBjYjsKICAgICAgICB9CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIHJldHVybiBhIDwgYjsKICAgICAgICB9CiAgICB9KTsKCiAgICBmb3IgKGF1dG8gdmFsdWUgOiB2MSkgewogICAgICAgIGNvdXQgPDwgdmFsdWUgPDwgIiAiOwogICAgfQoKICAgIGNvdXQgPDwgZW5kbDsKICAgIHN0YWJsZV9zb3J0KHYyLmJlZ2luKCksIHYyLmVuZCgpLCBbXShpbnQgYSwgaW50IGIpIHsKICAgICAgICBpbnQgY2EgPSBjb3VudE9kZChhKTsKICAgICAgICBpbnQgY2IgPSBjb3VudE9kZChiKTsKCiAgICAgICAgcmV0dXJuIGNhIDwgY2I7CgogICAgfSk7CgogICAgZm9yIChhdXRvIHZhbHVlIDogdjIpIHsKICAgICAgICBjb3V0IDw8IHZhbHVlIDw8ICIgIjsKICAgIH0KICAgIHJldHVybiAwOwp9Cgo=