///minalataZADACHI
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;
struct Node {
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int value) {
        this->value = value;
    }
};
class BST {
    Node* root = nullptr;
    Node* _add(int value, Node* current) {
        if (!current) {
            return new Node(value);
        }
        if (current->value < value) {
            current->right =  _add(value, current->right);
        }
        else if(current->value > value){
            current->left =  _add(value, current->left);
        }
        return current;
    }
    void _print(Node* current) const {
        if (current != nullptr) {
            cout << current->value << " ";
            _print(current->left);
            _print(current->right);
        }
    }
    Node* _remove(int value, Node* current) {
        if (current == nullptr) {
            return nullptr;
        }
        if (current->value > value) {
            current->left = _remove(value, current->left);
        }
        else if (current->value < value) {
            current->right = _remove(value, current->right);
        }
        else {
            if (current->left == nullptr && current->right == nullptr) {
                free(current);
                return nullptr;
            }
            else if (current->left == nullptr) {
                Node* temp = current->right;
                free(current);
                return temp;
            }
            else if(current->right == nullptr){
                Node* temp = current->left;
                free(current);
                return temp;
            }
            else {
                Node* temp = current->right;
                while (temp->left != nullptr) {
                    temp = temp->left;
                }
                current->value = temp->value;
                current->right = _remove(current->value, current->right);
            }
        }
        return current;
    }
    void _print_odd_layers(Node* current, bool isOdd) {
        if (current == nullptr) return;
        if (isOdd == true) {
            cout << current->value<<" ";
        }
        _print_odd_layers(current->left, !isOdd);
        _print_odd_layers(current->right, !isOdd);
    }

public:
    BST() {
        root = nullptr;
    }
    void add(int value) {
        root = _add(value, root);
    }
    void print() const {
        _print(root);
    }
    void remove(int value) {
        root = _remove(value, root);
    }
    void print_odd_layers() {
        _print_odd_layers(root, true);
    }
};
int main() {
    int operations;
    cin >> operations;
    BST bst;
    for (int i = 0; i < operations; i++) {
        string input;
        cin >> input;
        if (input == "add") {
            int current;
            cin >> current;
            bst.add(current);
        }
        else if (input == "print") {
            bst.print();
        }
        else if (input == "print_odd_layers") {
            bst.print_odd_layers();
        }
        else if (input == "remove") {
            int value;
            cin >> value;
            bst.remove(value);
        }
    }
}