#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Insert into BST
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

void inorder(TreeNode* root, vector<int>& evenList, vector<int>& oddList) {
    if (!root) return;
    inorder(root->left, evenList, oddList);
    if (root->val % 2 == 0) evenList.push_back(root->val);
    else oddList.push_back(root->val);
    inorder(root->right, evenList, oddList);
}

int main() {
    int n;
    cin >> n;
    if (n < -100 || n > 100) {
        cout << "Invalid input" << endl;
        return 0;
    }

    TreeNode* root = nullptr;
    bool invalid = false;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        if (val < -1000 || val > 1000) {
            invalid = true;
        }
        root = insert(root, val);
    }

    if (invalid) {
        cout << "Invalid input" << endl;
        return 0;
    }

    vector<int> evenList, oddList;
    inorder(root, evenList, oddList);

    for (int i = 0; i < evenList.size(); i++) {
        if (i > 0) cout << " ";
        cout << evenList[i];
    }
    cout << endl;
    for (int i = 0; i < oddList.size(); i++) {
        if (i > 0) cout << " ";
        cout << oddList[i];
    }
    cout << endl;

    return 0;
}