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

// Node structure
struct Node {
    int value;
    string color;
    Node* left;
    Node* right;
    Node(int v, string c) : value(v), color(c), left(nullptr), right(nullptr) {}
};

// Function to insert a node into the tree
Node* insert(Node* root, int value, string color) {
    if (root == nullptr) {
        return new Node(value, color);
    }
    if (value < root->value) {
        root->left = insert(root->left, value, color);
    } else {
        root->right = insert(root->right, value, color);
    }
    return root;
}

// Function to traverse and print tree in preorder
void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->value << " ";
    preorder(root->left);
    preorder(root->right);
}

// Function to traverse and print tree in inorder
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->value << " ";
    inorder(root->right);
}

// Function to traverse and print tree in postorder
void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->value << " ";
}

//Function to remove nodes with a specific color
Node* removeNode(Node* root, int valueToRemove, string colorToRemove) {
    if (root == nullptr) return nullptr;
    root->left = removeNode(root->left, valueToRemove, colorToRemove);
    root->right = removeNode(root->right, valueToRemove, colorToRemove);
    if (root->value == valueToRemove && root->color == colorToRemove) {
        // cout << "Removing node with value " << root->value << " and color " << root->color << endl;
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        } else {
            Node* temp = root->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            root->value = temp->value;
            root->color = temp->color;
            root->right = removeNode(root->right, valueToRemove, colorToRemove);
        }
    }
    return root;
}

//Function to remove nodes with a specific color
Node* removeColor(Node* root, string colorToRemove) {
    if (root == nullptr) return nullptr;
    root->left = removeColor(root->left, colorToRemove);
    root->right = removeColor(root->right, colorToRemove);
    if (root->color == colorToRemove) {
        // cout << "Removing node with value " << root->value << " and color " << root->color << endl;
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        } else {
            Node* temp = root->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            root->value = temp->value;
            root->color = temp->color;
            root->right = removeNode(root->right, temp->value, temp->color);
        }
    }
    return root;
}

int main() {
    Node* root = nullptr;
    int value;
    string color;

    // Input nodes
    while (true) {
        cin >> value;
        cin >> color;
        if (value == -1 && color == "null") break;
       
        root = insert(root, value, color);
    }

    // Input color to remove
    cin >> color;
    
    // Remove nodes with the specified color
    root = removeColor(root, color);

    // Print the result
    cout << "Preorder : ";
    preorder(root);
    cout << endl << "Inorder : ";
    inorder(root);
    cout << endl << "Postorder : ";
    postorder(root);
    cout << endl;

    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gTm9kZSBzdHJ1Y3R1cmUKc3RydWN0IE5vZGUgewogICAgaW50IHZhbHVlOwogICAgc3RyaW5nIGNvbG9yOwogICAgTm9kZSogbGVmdDsKICAgIE5vZGUqIHJpZ2h0OwogICAgTm9kZShpbnQgdiwgc3RyaW5nIGMpIDogdmFsdWUodiksIGNvbG9yKGMpLCBsZWZ0KG51bGxwdHIpLCByaWdodChudWxscHRyKSB7fQp9OwoKLy8gRnVuY3Rpb24gdG8gaW5zZXJ0IGEgbm9kZSBpbnRvIHRoZSB0cmVlCk5vZGUqIGluc2VydChOb2RlKiByb290LCBpbnQgdmFsdWUsIHN0cmluZyBjb2xvcikgewogICAgaWYgKHJvb3QgPT0gbnVsbHB0cikgewogICAgICAgIHJldHVybiBuZXcgTm9kZSh2YWx1ZSwgY29sb3IpOwogICAgfQogICAgaWYgKHZhbHVlIDwgcm9vdC0+dmFsdWUpIHsKICAgICAgICByb290LT5sZWZ0ID0gaW5zZXJ0KHJvb3QtPmxlZnQsIHZhbHVlLCBjb2xvcik7CiAgICB9IGVsc2UgewogICAgICAgIHJvb3QtPnJpZ2h0ID0gaW5zZXJ0KHJvb3QtPnJpZ2h0LCB2YWx1ZSwgY29sb3IpOwogICAgfQogICAgcmV0dXJuIHJvb3Q7Cn0KCi8vIEZ1bmN0aW9uIHRvIHRyYXZlcnNlIGFuZCBwcmludCB0cmVlIGluIHByZW9yZGVyCnZvaWQgcHJlb3JkZXIoTm9kZSogcm9vdCkgewogICAgaWYgKHJvb3QgPT0gbnVsbHB0cikgcmV0dXJuOwogICAgY291dCA8PCByb290LT52YWx1ZSA8PCAiICI7CiAgICBwcmVvcmRlcihyb290LT5sZWZ0KTsKICAgIHByZW9yZGVyKHJvb3QtPnJpZ2h0KTsKfQoKLy8gRnVuY3Rpb24gdG8gdHJhdmVyc2UgYW5kIHByaW50IHRyZWUgaW4gaW5vcmRlcgp2b2lkIGlub3JkZXIoTm9kZSogcm9vdCkgewogICAgaWYgKHJvb3QgPT0gbnVsbHB0cikgcmV0dXJuOwogICAgaW5vcmRlcihyb290LT5sZWZ0KTsKICAgIGNvdXQgPDwgcm9vdC0+dmFsdWUgPDwgIiAiOwogICAgaW5vcmRlcihyb290LT5yaWdodCk7Cn0KCi8vIEZ1bmN0aW9uIHRvIHRyYXZlcnNlIGFuZCBwcmludCB0cmVlIGluIHBvc3RvcmRlcgp2b2lkIHBvc3RvcmRlcihOb2RlKiByb290KSB7CiAgICBpZiAocm9vdCA9PSBudWxscHRyKSByZXR1cm47CiAgICBwb3N0b3JkZXIocm9vdC0+bGVmdCk7CiAgICBwb3N0b3JkZXIocm9vdC0+cmlnaHQpOwogICAgY291dCA8PCByb290LT52YWx1ZSA8PCAiICI7Cn0KCi8vRnVuY3Rpb24gdG8gcmVtb3ZlIG5vZGVzIHdpdGggYSBzcGVjaWZpYyBjb2xvcgpOb2RlKiByZW1vdmVOb2RlKE5vZGUqIHJvb3QsIGludCB2YWx1ZVRvUmVtb3ZlLCBzdHJpbmcgY29sb3JUb1JlbW92ZSkgewogICAgaWYgKHJvb3QgPT0gbnVsbHB0cikgcmV0dXJuIG51bGxwdHI7CiAgICByb290LT5sZWZ0ID0gcmVtb3ZlTm9kZShyb290LT5sZWZ0LCB2YWx1ZVRvUmVtb3ZlLCBjb2xvclRvUmVtb3ZlKTsKICAgIHJvb3QtPnJpZ2h0ID0gcmVtb3ZlTm9kZShyb290LT5yaWdodCwgdmFsdWVUb1JlbW92ZSwgY29sb3JUb1JlbW92ZSk7CiAgICBpZiAocm9vdC0+dmFsdWUgPT0gdmFsdWVUb1JlbW92ZSAmJiByb290LT5jb2xvciA9PSBjb2xvclRvUmVtb3ZlKSB7CiAgICAgICAgLy8gY291dCA8PCAiUmVtb3Zpbmcgbm9kZSB3aXRoIHZhbHVlICIgPDwgcm9vdC0+dmFsdWUgPDwgIiBhbmQgY29sb3IgIiA8PCByb290LT5jb2xvciA8PCBlbmRsOwogICAgICAgIGlmIChyb290LT5sZWZ0ID09IG51bGxwdHIpIHsKICAgICAgICAgICAgTm9kZSogdGVtcCA9IHJvb3QtPnJpZ2h0OwogICAgICAgICAgICBkZWxldGUgcm9vdDsKICAgICAgICAgICAgcmV0dXJuIHRlbXA7CiAgICAgICAgfSBlbHNlIGlmIChyb290LT5yaWdodCA9PSBudWxscHRyKSB7CiAgICAgICAgICAgIE5vZGUqIHRlbXAgPSByb290LT5sZWZ0OwogICAgICAgICAgICBkZWxldGUgcm9vdDsKICAgICAgICAgICAgcmV0dXJuIHRlbXA7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgTm9kZSogdGVtcCA9IHJvb3QtPnJpZ2h0OwogICAgICAgICAgICB3aGlsZSAodGVtcC0+bGVmdCAhPSBudWxscHRyKSB7CiAgICAgICAgICAgICAgICB0ZW1wID0gdGVtcC0+bGVmdDsKICAgICAgICAgICAgfQogICAgICAgICAgICByb290LT52YWx1ZSA9IHRlbXAtPnZhbHVlOwogICAgICAgICAgICByb290LT5jb2xvciA9IHRlbXAtPmNvbG9yOwogICAgICAgICAgICByb290LT5yaWdodCA9IHJlbW92ZU5vZGUocm9vdC0+cmlnaHQsIHZhbHVlVG9SZW1vdmUsIGNvbG9yVG9SZW1vdmUpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiByb290Owp9CgovL0Z1bmN0aW9uIHRvIHJlbW92ZSBub2RlcyB3aXRoIGEgc3BlY2lmaWMgY29sb3IKTm9kZSogcmVtb3ZlQ29sb3IoTm9kZSogcm9vdCwgc3RyaW5nIGNvbG9yVG9SZW1vdmUpIHsKICAgIGlmIChyb290ID09IG51bGxwdHIpIHJldHVybiBudWxscHRyOwogICAgcm9vdC0+bGVmdCA9IHJlbW92ZUNvbG9yKHJvb3QtPmxlZnQsIGNvbG9yVG9SZW1vdmUpOwogICAgcm9vdC0+cmlnaHQgPSByZW1vdmVDb2xvcihyb290LT5yaWdodCwgY29sb3JUb1JlbW92ZSk7CiAgICBpZiAocm9vdC0+Y29sb3IgPT0gY29sb3JUb1JlbW92ZSkgewogICAgICAgIC8vIGNvdXQgPDwgIlJlbW92aW5nIG5vZGUgd2l0aCB2YWx1ZSAiIDw8IHJvb3QtPnZhbHVlIDw8ICIgYW5kIGNvbG9yICIgPDwgcm9vdC0+Y29sb3IgPDwgZW5kbDsKICAgICAgICBpZiAocm9vdC0+bGVmdCA9PSBudWxscHRyKSB7CiAgICAgICAgICAgIE5vZGUqIHRlbXAgPSByb290LT5yaWdodDsKICAgICAgICAgICAgZGVsZXRlIHJvb3Q7CiAgICAgICAgICAgIHJldHVybiB0ZW1wOwogICAgICAgIH0gZWxzZSBpZiAocm9vdC0+cmlnaHQgPT0gbnVsbHB0cikgewogICAgICAgICAgICBOb2RlKiB0ZW1wID0gcm9vdC0+bGVmdDsKICAgICAgICAgICAgZGVsZXRlIHJvb3Q7CiAgICAgICAgICAgIHJldHVybiB0ZW1wOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIE5vZGUqIHRlbXAgPSByb290LT5yaWdodDsKICAgICAgICAgICAgd2hpbGUgKHRlbXAtPmxlZnQgIT0gbnVsbHB0cikgewogICAgICAgICAgICAgICAgdGVtcCA9IHRlbXAtPmxlZnQ7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcm9vdC0+dmFsdWUgPSB0ZW1wLT52YWx1ZTsKICAgICAgICAgICAgcm9vdC0+Y29sb3IgPSB0ZW1wLT5jb2xvcjsKICAgICAgICAgICAgcm9vdC0+cmlnaHQgPSByZW1vdmVOb2RlKHJvb3QtPnJpZ2h0LCB0ZW1wLT52YWx1ZSwgdGVtcC0+Y29sb3IpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiByb290Owp9CgppbnQgbWFpbigpIHsKICAgIE5vZGUqIHJvb3QgPSBudWxscHRyOwogICAgaW50IHZhbHVlOwogICAgc3RyaW5nIGNvbG9yOwoKICAgIC8vIElucHV0IG5vZGVzCiAgICB3aGlsZSAodHJ1ZSkgewogICAgICAgIGNpbiA+PiB2YWx1ZTsKICAgICAgICBjaW4gPj4gY29sb3I7CiAgICAgICAgaWYgKHZhbHVlID09IC0xICYmIGNvbG9yID09ICJudWxsIikgYnJlYWs7CiAgICAgICAKICAgICAgICByb290ID0gaW5zZXJ0KHJvb3QsIHZhbHVlLCBjb2xvcik7CiAgICB9CgogICAgLy8gSW5wdXQgY29sb3IgdG8gcmVtb3ZlCiAgICBjaW4gPj4gY29sb3I7CiAgICAKICAgIC8vIFJlbW92ZSBub2RlcyB3aXRoIHRoZSBzcGVjaWZpZWQgY29sb3IKICAgIHJvb3QgPSByZW1vdmVDb2xvcihyb290LCBjb2xvcik7CgogICAgLy8gUHJpbnQgdGhlIHJlc3VsdAogICAgY291dCA8PCAiUHJlb3JkZXIgOiAiOwogICAgcHJlb3JkZXIocm9vdCk7CiAgICBjb3V0IDw8IGVuZGwgPDwgIklub3JkZXIgOiAiOwogICAgaW5vcmRlcihyb290KTsKICAgIGNvdXQgPDwgZW5kbCA8PCAiUG9zdG9yZGVyIDogIjsKICAgIHBvc3RvcmRlcihyb290KTsKICAgIGNvdXQgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQoK

MTEgeWVsbG93CjIwIHllbGxvdwo3IHB1cnBsZQoxIG9yYW5nZQo5IHllbGxvdwoxMiBwdXJwbGUKMjIgb3JhbmdlCi0xIG51bGwKeWVsbG93Cg==

11 yellow
20 yellow
7 purple
1 orange
9 yellow
12 purple
22 orange
-1 null
yellow