vector<int> evens, odds;
for (int n : input) {
    if (n % 2 == 0) {
        evens.push_back(n);
    } else {
        odds.push_back(n);
    }
}

sort(odds.begin(), odds.end());
sort(evens.begin(), evens.end());

// Print odds first
for (size_t i = 0; i < odds.size(); ++i) {
    if (i > 0) cout << " ";
    cout << odds[i];
}
cout << endl;

// Print evens
for (size_t i = 0; i < evens.size(); ++i) {
    if (i > 0) cout << " ";
    cout << evens[i];
}
cout << endl;

return 0;