#include <iostream>

using namespace std;

class Node
{
public:
    Node *left,*right,*parent;
    int val;
    char color='B';
    int low,high,mx;

    void moveDown(Node *nParent)
    {
        if (parent != NULL)
        {
            if (isOnLeft())
            {
                parent->left = nParent;
            }
            else
            {
                parent->right = nParent;
            }
        }
        nParent->parent = parent;
        parent = nParent;
    }

    bool isOnLeft()
    {
        return this == parent->left;
    }

    void SwapColor(Node*node)
    {
        if (node->color=='R')
            node->color='B';
        else
            node->color='R';
    }

};
class RBT
{

public:
    Node *root= new Node;
    void RightRotate(Node *x)
    {
        // new parent will be node's left child
        Node *nParent = x->left;

        // update root if current node is root
        if (x == root)
            root = nParent;

        x->moveDown(nParent);

        // connect x with new parent's right element
        x->left = nParent->right;
        // connect new parent's right element with node
        // if it is not null
        if (nParent->right != NULL)
            nParent->right->parent = x;

        // connect new parent with x
        nParent->right = x;
    }


    void LeftRotate(Node *x)
    {
        // new parent will be node's right child
        Node *nParent = x->right;

        // update root if current node is root
        if (x == root)
            root = nParent;

        x->moveDown(nParent);

        // connect x with new parent's left element
        x->right = nParent->left;
        // connect new parent's left element with node
        // if it is not null
        if (nParent->left != NULL)
            nParent->left->parent = x;

        // connect new parent with x
        nParent->left = x;
    }
    void inorder(Node *root)
{
    if (root == NULL)
        return;

    inorder(root->left);

    cout << "[" << root->low << ", " << root->high << "]"
         << " max = " << root->mx << endl;

    inorder(root->right);
}
void preorder(Node *root)
{
    if (root == NULL)
        return;

    cout << "[ " << root->low << " " << root->high << " ]"
         << " max = " << root->mx << endl;
    inorder(root->left);
    inorder(root->right);
}


Node* add(Node* node, int low,int high)
    {
        cout<<"hi from add func\n";
        int l = root->low;

        if (root == NULL)
        {
            cout<<"root added\n";
            return root; //bfkar a5alii myrturnesh
        }

        else if (low<l)
            {root->left = add(root->left, low,high);
            root->left->parent = root; //not sure
            }
        else if (low>l)
        {
            root->right = add(root->right, low,high);
            root->right->parent = root; //not sure
        }


        else{
            cout<<"sth wrong in adding\n";
            return node;
        }

        if (root->mx < high) //ancesstor fixation
            root->mx = high;

        cout<<"node added succ\n";

        return root;
    }

    void Insert(int high,int low)
    {
        cout<<"hi from insert func\n";
        if(root==NULL)
        {
            root->mx=high;
            root->low=low;
            root->high=high;
            root->left = root->right = NULL;
            add(root,high,low);
        }
        /*return;
        if(root==NULL)
        {
            add(root,high,low);
            root->color='B';
            cout<<"Tree of only Root fixed successfuly\n";
        } */
       else
        {
            Node *x=new Node;
            add(x,high,low);
            x->color='R';

            Node *uncle=new Node;

            while(x!=root && x->parent->color!='R')
            {
                if(x->parent==x->parent->parent->left) //law baba el ebn el as3'ar
                {
                    uncle=x->parent->parent->right;

                    if (uncle->color=='R')
                    {
                        x->parent->color = 'B';
                        uncle->color = 'B';
                        x->parent->parent->color = 'R';
                        x = x->parent->parent;

                    }
                    else //law 3amy eswed
                    {
                        //left left case
                        // (p is left child of g and x is left child of p)
                        if(x->parent==x->parent->parent->left && x==x->parent->left)
                        {
                            RightRotate(x->parent->parent);
                            x->SwapColor(x->parent->parent);
                            x->SwapColor(x->parent);

                        }

                        //left right case
                        else if(x->parent==x->parent->parent->left && x==x->parent->right)
                        {
                            LeftRotate(x->parent);
                            RightRotate(x->parent->parent);
                            x->SwapColor(x->parent->parent);
                            x->SwapColor(x->parent);

                        }
                        //right right
                        else if (x->parent==x->parent->parent->right && x==x->parent->right)
                        {
                            LeftRotate(x->parent->parent);
                            x->SwapColor(x->parent->parent);
                            x->SwapColor(x->parent);

                        }
                        else
                        {
                            RightRotate(x->parent);
                            LeftRotate(x->parent->parent);
                            x->SwapColor(x->parent->parent);
                            x->SwapColor(x->parent);

                        }

                    }


                }



            }
        cout<<"tree fixed\n";
        }

    }

};




int main()
{
    RBT MyTree;
    int n=0;
    cout<<"how many nodes\n";
    cin>>n;
    cout << "insert inputs" << endl;
    int x,y;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        cin>>y;
        MyTree.Insert(x,y);

    }
    cout<<"preorder\n";
    MyTree.preorder(MyTree.root);
    cout<<"\n";
    cout<<"inorder\n";
    MyTree.inorder(MyTree.root);
    return 0;
}