#include <iostream>
using namespace std;

class Node
{
public:
    Node* left;
    Node* right;
    char height;
    int key;
    string data;

    Node(int key,string* data);
};

Node::Node(int key,string* data)
{
    this->data.reserve(196); // size of int is 4 byte so 4 + 196 = 200
    this->key = key;
    this->data = (*data);
    height = 0;
    left = nullptr;
    right = nullptr;
}

class AVLtree
{
private:
    Node* root;

    bool Insert(int k,string* d, Node** leaf);

    void PrettyPrint(Node* n, string pre);

    void InOrder(Node* n);

    Node* Search(int k,Node* leaf);

    void deleteA(Node** currPtr);

    void deleteBleft(Node** currPtr);

    void deleteBright(Node** currPtr);

    void deleteC(Node** currPtr);

    bool SetRightest(Node** n,Node*** ret);

    char Height(Node* n);

    void RightRotate(Node** n);

    void LeftRotate(Node** n);

    char NewHeight(Node* n);

    bool Remove(int key,Node** n);

    void Free(Node* n);

public:
    void Add(int key,string data);

    string Search(int key);

    void InOrder();

    void Remove(int key);

    void Clear();

    AVLtree();

    ~AVLtree();

    void PrettyPrint();


};

bool AVLtree::Insert(int k,string* d, Node** leaf)
{
    bool h = false;
    if(k<(*leaf)->key)
    {
        if((*leaf)->left!=nullptr)
        {
            h = Insert(k,d,&((*leaf)->left));
            if (h)
            {
                if((Height((*leaf)->right)-Height((*leaf)->left))<-1)
                {
                    if(Height((*leaf)->left->right)-Height((*leaf)->left->left)>0)
                    {
                        LeftRotate(&((*leaf)->left));
                    }
                    RightRotate(leaf);
                }
            }
        }
        else
        {
            (*leaf)->left = new Node(k,d);
            h=true;
        }
    }
    else
    {
        if(k>(*leaf)->key)
        {
            if((*leaf)->right!=nullptr)
            {
                h = Insert(k,d,&((*leaf)->right));
                if(h)
                {
                    if((Height((*leaf)->right)-Height((*leaf)->left))>1)
                    {
                        if(Height((*leaf)->right->right)-Height((*leaf)->right->left)<0)
                        {
                            RightRotate(&((*leaf)->right));
                        }
                        LeftRotate(leaf);
                    }
                }
            }
            else
            {
                (*leaf)->right = new Node(k,d);
                h = true;
            }
        }
        else
        {
            (*leaf)->data = (*d); //node is already in the tree
        }
    }
    if (h)
    {
        char nh = NewHeight((*leaf));
        if (nh!=(*leaf)->height)
        {
            (*leaf)->height = nh;
        }
        else
        {
            h=false;
        }
    }
    return h;
}

void AVLtree::PrettyPrint(Node* n, string pre)
{
    if(n!=nullptr)
    {
        cout<<pre<<(n->key)<<" "<<(n->data)<<" "<<(int)(n->height)<<"\n";
        PrettyPrint(n->left,"  "+pre);
        PrettyPrint(n->right,"  "+pre);
    }
}

bool AVLtree::Remove(int key,Node** n)
{
    bool h = false; // height changed
    bool d = false; // child has been removed
    if((*n)!=nullptr)
    {
        if((*n)->key==key)
        {
            d = true;
            Node** currPtr = n;
            if((*currPtr)->left==nullptr&&(*currPtr)->right==nullptr)
            {
                deleteA(currPtr);
            }
            else
            {
                if((*currPtr)->left!=nullptr&&(*currPtr)->right==nullptr)
                {
                    deleteBleft(currPtr);
                    h = true;
                }
                else
                {
                    if((*currPtr)->left==nullptr&&(*currPtr)->right!=nullptr)
                    {
                        deleteBright(currPtr);
                        h = true;
                    }
                    else
                    {
                        if((*currPtr)->left!=nullptr&&(*currPtr)->right!=nullptr)
                        {
                            deleteC(currPtr);
                            h = true;
                        }
                    }
                }
            }
        }
        else
        {
            if(key<((*n)->key))
            {
                h = Remove(key,&((*n)->left));
                if(h)
                {
                    if((Height((*n)->right)-Height((*n)->left))>1)
                    {
                        d = true;
                        if(Height((*n)->right->right)-Height((*n)->right->left)<0)
                        {
                            RightRotate(&((*n)->right));
                        }
                        LeftRotate(n);
                    }
                }
            }
            else
            {
                if (key>((*n)->key))
                {
                    h = Remove(key,&((*n)->right));
                    if (h)
                    {
                        if((Height((*n)->right)-Height((*n)->left))<-1)
                        {
                            d = true;
                            if(Height((*n)->left->right)-Height((*n)->left->left)>0)
                            {
                                LeftRotate(&((*n)->left));
                            }
                            RightRotate(n);
                        }
                    }
                }
            }
        }
        if (h)
        {
            char nh = NewHeight((*n));
            if (nh!=(*n)->height)
            {
                (*n)->height = nh;
            }
            else
            {
                h=false;
            }
        }
    }
    return (h||d);
}

void AVLtree::InOrder(Node* n)
{
    if(n!=nullptr)
    {
        InOrder(n->left);
        cout<<"\n"<<n->key;
        InOrder(n->right);
    }
}

Node* AVLtree::Search(int k,Node* leaf)
{
    if (leaf==nullptr)
    {
        return nullptr;
    }
    if (leaf->key==k)
    {
        return leaf;
    }
    else
    {
        if(k<leaf->key)
        {
            return Search(k,leaf->left);
        }
        else
        {
            return Search(k,leaf->right);
        }
    }
}
void AVLtree::deleteA(Node** currPtr) //when Node has no children
{
    delete (*currPtr);
    (*currPtr)=nullptr;
}

void AVLtree::deleteBleft(Node** currPtr) // when node has only the left child
{
    Node* l = (*currPtr);
    (*currPtr)=(*currPtr)->left;
    delete (l);
}

void AVLtree::deleteBright(Node** currPtr) //when node has only the right child
{
    Node* l = (*currPtr);
    (*currPtr)=(*currPtr)->right;
    delete (l);
}

void AVLtree::deleteC(Node** currPtr) //when node has both child
{
    Node** leftMax;  //the node with the greatest value in left subtree  to replace current node
    SetRightest(&((*currPtr)->left),&leftMax);
    Node* oldleft = (*leftMax)->left;
    Node* old = (*currPtr);
    *currPtr = *leftMax;
    *leftMax = oldleft;
    (*currPtr)->left = old->left;
    (*currPtr)->right = old->right;
    if((Height((*currPtr)->right)-Height((*currPtr)->left))>1) //balance also needs to be checked here
    {
        if(Height((*currPtr)->right->right)-Height((*currPtr)->right->left)<0)
        {
            RightRotate(&((*currPtr)->right));
        }
        LeftRotate(currPtr);
    }
    (*currPtr)->height = NewHeight(*currPtr);
    delete old;

}

bool AVLtree::SetRightest(Node** n,Node*** ret) //to get pointer to pointer to the greatest node in left subtree
{
    bool h = false;
    if((*n)->right!=nullptr)
    {
        h = SetRightest(&((*n)->right),ret);
        if(h)
        {
            if((Height((*n)->right)-Height((*n)->left))<-1)
            {
                if(Height((*n)->left->right)-Height((*n)->left->left)>0)
                {
                    LeftRotate(&((*n)->left));
                }
                RightRotate(n);
            }
            char nh = NewHeight((*n));
            if(nh<(*n)->height)
            {
                (*n)->height=nh;
            }
            else
            {
                h = false;
            }
        }
    }
    else
    {
        (*ret) = n;
        (*n)->height=-1; //height of non-existing subtree
        h=true;
    }
    return h;
}

char AVLtree::Height(Node* n) //height of subtree + 1
{
    if(n==nullptr)
    {
        return 0;
    }
    else
    {
        return (n->height)+1;
    }
}

void AVLtree::RightRotate(Node** n)
{
    Node* temp = ((*n)->left);
    ((*n)->left)=temp->right;
    temp->right=(*n);
    (*n)=temp;
    (*n)->right->height=NewHeight((*n)->right);
    (*n)->height = NewHeight(*n);
}

void AVLtree::LeftRotate(Node** n)
{
    Node* temp = ((*n)->right);
    ((*n)->right)=temp->left;
    temp->left=(*n);
    (*n)=temp;
    (*n)->left->height=NewHeight((*n)->left);
    (*n)->height = NewHeight(*n);
}

char AVLtree::NewHeight(Node* n)
{
    char lh = Height(n->left);
    char rh = Height(n->right);
    if(rh>lh)
    {
        return rh;
    }
    else
        return lh;
}

void AVLtree::Add(int key,string data)
{
    if (root != nullptr)
    {
        Insert(key,&data,&root);
    }
    else
    {
        root = new Node(key,&data);
    }
}

string AVLtree::Search(int key)  //returns data value of a node or nullptr if node was not found
{
    Node* temp = Search(key,root);
    if (temp!=nullptr)
    {
        return temp->data;
    }
    else
    {
        return "none";
    }
}

void AVLtree::InOrder()
{
    InOrder(root);
}

void AVLtree::Remove(int key)
{
    Remove(key,(&root));
}

void AVLtree::Free(Node* n)
{
    if(n!=nullptr)
    {
        Free(n->left);
        Free(n->right);
        delete n;
    }
}

void AVLtree::Clear()
{
    Free(root);
    root = nullptr;
}

AVLtree::AVLtree()
{
    root = nullptr;
}

AVLtree::~AVLtree()
{
    Clear();
}

void AVLtree::PrettyPrint()
{
    PrettyPrint(root,   "|--");
}

int main()
{
    AVLtree myTree = AVLtree();
    int in;
    while (true) //simple test
    {
        cin>>in;
        if(in == 0)
        {
            break;
        }
        if(in>0)
        {
            myTree.Add(in,"");
            myTree.PrettyPrint();
            cout<<"\n\n";
        }
        else
        {
            myTree.Remove(-1*in);
            myTree.PrettyPrint();
            cout<<"\n\n";
        }
    }
    myTree.Clear();
    return 0;
}