#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
    int data;
    Node *left, *right;
    Node(int data) : data(data), left(nullptr), right(nullptr) {}
};

class BST
{
private:

    Node* root;

    Node* insertRec(int val, Node* root)
    {
        if (root == nullptr)
            return new Node(val);

        if (root->data > val)
            root->left = insertRec(val, root->left);
        else if (root->data < val)
            root->right = insertRec(val, root->right);
        return root;
    }

    Node* removeRec(int val, Node* root)
    {
        if (root == nullptr)
            return nullptr;

        if (root->data > val)
            root->left = removeRec(val, root->left);
        else if (root->data < val)
            root->right = removeRec(val, root->right);
        else
        {
            if (root->right == nullptr)
            {
                Node* tmp = root->left;
                delete root;
                return tmp;
            }
            else if (root->left == nullptr)
            {
                Node* tmp = root->right;
                delete root;
                return tmp;
            }

            Node* tmp = root->right;
            while (tmp->left != nullptr)
                tmp = tmp->left;

            root->data = tmp->data;
            root->right = removeRec(tmp->data, root->right);
        }

        return root;
    }

    void printRec(Node* root)
    {
        if (root)
        {
            cout << root->data << " ";
            printRec(root->left);
            printRec(root->right);
        }
    }

public:

    BST()
    {
        root = nullptr;
    }

    void insert(int val)
    {
        root = insertRec(val, root);
    }

    void remove(int val)
    {
        root = removeRec(val, root);
    }

    void print()
    {
        printRec(root);
    }

    void printOddLayers()
    {
        queue<Node*> q;
        q.push(root);

        int currSize = 1;
        int level = 1;

        while (!q.empty())
        {
            for (int i = 0; i < currSize; i++)
            {
                Node* tmp = q.front();
                q.pop();

                if (level % 2 != 0)
                    cout << tmp->data << " ";

                if (tmp->left)
                    q.push(tmp->left);
                if (tmp->right)
                    q.push(tmp->right);
            }

            currSize = q.size();
            level++;
        }
    }
};

int main() {

    int N;
    cin >> N;

    BST b;

    int input;
    string command;
    for (int i = 0; i < N; i++)
    {
        cin >> command;
        if (command == "add")
        {
            cin >> input;
            b.insert(input);
        }
        else if (command == "print")
        {
            b.print();
        }
        else if (command == "remove")
        {
            cin >> input;
            b.remove(input);
        }
        else if (command == "print_odd_layers")
        {
            b.printOddLayers();
        }
    }

    return 0;
}