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

class Node {
public:
    int key;
    Node* left;
    Node* right;
    int height;
    int bf; // Balance Factor

    Node(int key) {
        this->key = key;
        this->left = nullptr;
        this->right = nullptr;
        this->height = 1;
        this->bf = 0;
    }
};

Node* getAVLNode(int key) {
    return new Node(key);
}

int height(Node* T) {
    return T ? T->height : 0;
}

Node* rotateLL(Node* x) {
    Node* y = x->left;
    x->left = y->right;
    y->right = x;

    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    x->bf = height(x->left) - height(x->right);
    y->bf = height(y->left) - height(y->right);

    return y;
}

Node* rotateRR(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;

    x->height = 1 + max(height(x->left), height(x->right));
    y->height = 1 + max(height(y->left), height(y->right));

    x->bf = height(x->left) - height(x->right);
    y->bf = height(y->left) - height(y->right);

    return y;
}

Node* rotateLR(Node* x) {
    x->left = rotateRR(x->left);
    return rotateLL(x);
}

Node* rotateRL(Node* x) {
    x->right = rotateLL(x->right);
    return rotateRR(x);
}

bool insertAVL(Node* T, int newKey) {
    Node* p = T;
    Node* q = nullptr;
    stack<Node*> nodeStack;
    Node* x = nullptr;
    Node* f = nullptr;

    // find position to insert newKey while storing parent nodes on stack
    while (p != nullptr) {
        if (newKey == p->key) {
            cout << "Key already exists!" << endl;
            return false;  // Avoid inserting duplicates
        }

        q = p;
        nodeStack.push(q);

        if (newKey < p->key) {
            p = p->left;
        } else {
            p = p->right;
        }
    }

    // create new node
    Node* y = getAVLNode(newKey);

    // insert y as a child of q
    if (T == nullptr) {
        T = y;
    } else if (newKey < q->key) {
        q->left = y;
    } else {
        q->right = y;
    }

    // update height and balancing factor while popping parent nodes from stack
    while (!nodeStack.empty()) {
        q = nodeStack.top();
        nodeStack.pop();
        q->height = 1 + max(height(q->left), height(q->right));
        q->bf = height(q->left) - height(q->right);

        if (q->bf > 1 || q->bf < -1) {
            if (x == nullptr) {
                x = q;
                f = nodeStack.empty() ? nullptr : nodeStack.top();
            }
        }
    }

    // If no imbalance found, return
    if (x == nullptr) return false;

    // Rebalance the tree
    if (x->bf > 1) {
        if (x->left->bf >= 0) {
            return rotateLL(x);
        } else {
            return rotateLR(x);
        }
    } else if (x->bf < -1) {
        if (x->right->bf <= 0) {
            return rotateRR(x);
        } else {
            return rotateRL(x);
        }
    }

    return true;
}

bool deleteAVL(Node* T, int deleteKey) {
    Node* p = T;
    Node* q = nullptr;
    stack<Node*> nodeStack;
    Node* x = nullptr;
    Node* f = nullptr;

    // Perform standard BST deletion
    while (p != nullptr && deleteKey != p->key) {
        q = p;
        nodeStack.push(q);
        if (deleteKey < p->key) {
            p = p->left;
        } else {
            p = p->right;
        }
    }

    if (p == nullptr) {
        cout << "Key not found!" << endl;
        return false; // deleteKey was not found
    }

    // Case 1: Node has two children
    if (p->left != nullptr && p->right != nullptr) {
        nodeStack.push(p);
        Node* tempNode = p;
        if (height(p->left) < height(p->right)) {
            p = p->right;
            while (p->left != nullptr) {
                nodeStack.push(p);
                p = p->left;
            }
        } else {
            p = p->left;
            while (p->right != nullptr) {
                nodeStack.push(p);
                p = p->right;
            }
        }
        tempNode->key = p->key;
        q = nodeStack.top();
        nodeStack.pop();
    }

    // Case 2: Node has 0 or 1 child
    if (p->left == nullptr && p->right == nullptr) {
        if (q == nullptr) {
            T = nullptr;
        } else if (q->left == p) {
            q->left = nullptr;
        } else {
            q->right = nullptr;
        }
    } else {
        Node* child = (p->left != nullptr) ? p->left : p->right;
        if (q == nullptr) {
            T = child;
        } else if (q->left == p) {
            q->left = child;
        } else {
            q->right = child;
        }
    }

    delete p;

    // Update height and balancing factor while popping parent nodes from stack
    while (!nodeStack.empty()) {
        q = nodeStack.top();
        nodeStack.pop();
        q->height = 1 + max(height(q->left), height(q->right));
        q->bf = height(q->left) - height(q->right);

        if (q->bf > 1 || q->bf < -1) {
            x = q;
            f = nodeStack.empty() ? nullptr : nodeStack.top();

            // Rebalance the tree
            if (x->bf > 1) {
                if (x->left->bf >= 0) {
                    T = rotateLL(x);
                } else {
                    T = rotateLR(x);
                }
            } else if (x->bf < -1) {
                if (x->right->bf <= 0) {
                    T = rotateRR(x);
                } else {
                    T = rotateRL(x);
                }
            }
        }
    }

    return true;
}

void inorder(Node* T) {
    if (T == nullptr) {
        return;
    }

    cout << "<";

    if (T->left != nullptr) { // 왼쪽 자식이 있을 때만 출력
        inorder(T->left);
    }

    cout << " " << T->key << " "; // 현재 노드의 키를 출력

    if (T->right != nullptr) { // 오른쪽 자식이 있을 때만 출력
        inorder(T->right);
    }

    cout << ">";
}

void clear(Node* T) {
    if (T == nullptr) {
        return;
    }
    clear(T->left);
    clear(T->right);
    delete T;
}


int main() {

    Node* root = nullptr;
    char operation;
    int key;

    while (cin >> operation >> key) {
        bool sucess = false; // 삽입, 삭제가 에러 상황을 만나지 않고 잘 수행되었는지
        if (operation == 'i') {
            sucess = insertAVL(root, key);
        }
        else if (operation == 'd') {
            sucess = deleteAVL(root, key);
        }
        if (sucess) {
            inorder(root);
            cout << endl;
        }
    }
    clear(root);
    return 0;
}