#include <bits/stdc++.h>
#define ll                                      long long int

#define fi                                      freopen("in.txt", "r", stdin)
#define fo                                      freopen("out.txt", "w", stdout)
#define m0(a) memset(a , 0 , sizeof(a))
#define m1(a) memset(a , -1 , sizeof(a))

#define Red 1
#define Black 2

#define NilValue -9999999999

using namespace std ;

class Node
{
public:
    Node* Parent ;
    Node* rightChild ;
    Node* leftChild ;
    ll Value ;
    ll Color ;

    Node()
    {
        Parent = rightChild = leftChild = 0 ;
        Value = 0 ;
        Color = Black ;
    }

    Node(ll a)
    {
        Parent = rightChild = leftChild = 0 ;
        Value = a;
        Color = Black ;
    }
};

Node* Nil ;


class RedBlackTree
{
public:
    Node* Root ;

    RedBlackTree()
    {
        Root = Nil ;
    }

    void leftRotate(Node *Curr);
    void rightRotate(Node *Curr);

    void Insert(Node *newVal);
    void insertFixUp(Node *newVal);

    Node* RBmin(Node *root);
    Node* RBmax(Node *root);
    Node* Search(ll value);
    void AscPrint(Node* n);

    void RBTransplant(Node *u, Node *v);
    void RBdelete(Node *toDeleteValue);
    void RBdeleteFixUp(Node *x);
};

Node* RedBlackTree::RBmax(Node *root)
{
    Node *x, *y ;
    y = Nil;
    x = root;

    while(x != Nil)
    {
        y = x ;
        x = x->rightChild;
    }
    return y;
}

Node* RedBlackTree::RBmin(Node *root)
{
    Node *x, *y ;
    y = Nil;
    x = root;

    while(x != Nil)
    {
        y = x ;
        x = x->leftChild ;
    }
    return y;
}


Node* RedBlackTree::Search(ll value)
{
    Node *x, *y ;
    y = Nil;
    x = Root;

    while(x != Nil)
    {
        y = x ;

        if(value > x->Value)
        {
            x = x->rightChild;
        }
        else if(value < x->Value)
        {
            x = x->leftChild;
        }
        else
        {
            return x ;
        }
    }
    return Nil;
}



void RedBlackTree::AscPrint(Node* n)
{
    if(n == Nil) return ;
    AscPrint(n->leftChild);
    cout << n->Value << " " ;
    AscPrint(n->rightChild);
    return ;
}


void RedBlackTree::RBdelete(Node *toDeleteValue)
{
    Node *y, *x ;
    y = toDeleteValue ;
    ll originial_Color_Of_Y ;
    originial_Color_Of_Y = y->Color ;

    if(toDeleteValue->leftChild == Nil)
    {
        x = toDeleteValue->rightChild;
        RBTransplant(toDeleteValue,toDeleteValue->rightChild);
    }
    else if(toDeleteValue->rightChild == Nil)
    {
        x = toDeleteValue->leftChild;
        RBTransplant(toDeleteValue,toDeleteValue->leftChild);
    }
    else
    {
        y = RBmin(toDeleteValue->rightChild);
        originial_Color_Of_Y = y->Color ;
        x = y->rightChild ;

        if(y->Parent == toDeleteValue)
        {
            x->Parent = y ;
        }
        else
        {
            RBTransplant(y, y->rightChild);
            y->rightChild = toDeleteValue->rightChild;
            y->rightChild->Parent = y ;
        }
        RBTransplant(toDeleteValue, y);
        y->leftChild = toDeleteValue->leftChild;
        y->leftChild->Parent = y ;
        y->Color = toDeleteValue->Color;
    }

    if(originial_Color_Of_Y == Black)
    {
        RBdeleteFixUp(x);
    }
}


void RedBlackTree::RBdeleteFixUp(Node *x)
{
    Node *w ;

    while(x != Root && x->Color == Black)
    {
        if(x == x->Parent->leftChild)
        {
            w = x->Parent->rightChild;

            if(w->Color == Red)
            {
                w->Color = Black ;
                x->Parent->Color = Red;
                leftRotate(x->Parent);
                w = x->Parent->rightChild ;
            }

            if(w->leftChild->Color == Black && w->rightChild->Color == Black)
            {
                w->Color = Red ;
                x = x->Parent ;
            }
            else
            {
                if(w->rightChild->Color == Black)
                {
                    w->leftChild->Color = Black ;
                    w->Color = Red ;
                    rightRotate(w);
                    w = x->Parent->rightChild;
                }
                w->Color = x->Parent->Color;
                x->Parent->Color = Black ;
                w->rightChild->Color = Black ;
                leftRotate(x->Parent);
                x = Root ;
            }

        }
        else /// x == x->Parent->rightChild
        {
            cout << "hi" << endl ;
            w = x->Parent->leftChild;

            if(w->Color == Red)
            {
                w->Color = Black ;
                x->Parent->Color = Red;
                rightRotate(x->Parent);
                w = x->Parent->leftChild ;
            }
            if(w->rightChild->Color == Black && w->leftChild->Color == Black)
            {
                w->Color = Red ;
                x = x->Parent ;
            }
            else
            {
                if(w->leftChild->Color == Black)
                {
                    w->rightChild->Color = Black ;
                    w->Color = Red ;
                    leftRotate(w);
                    w = x->Parent->leftChild;
                }
                w->Color = x->Parent->Color;
                x->Parent->Color = Black ;
                w->leftChild->Color = Black ;
                rightRotate(x->Parent);
                x = Root ;
            }


        }

    }
    x->Color = Black;

    return ;
}


void RedBlackTree::RBTransplant(Node *u, Node *v)
{
    if(u->Parent == Nil)
    {
        Root = v ;
        Root->Parent = Nil ;
    }
    else
    {
        if(u == u->Parent->leftChild)
        {
            u->Parent->leftChild = v ;
        }
        else
        {
            u->Parent->rightChild = v;
        }
    }

    v->Parent = u->Parent ;
    return ;
}

void RedBlackTree::leftRotate(Node *Curr)
{
    Node *currRightChild ;

    currRightChild = Curr->rightChild;


    Curr->rightChild = currRightChild->leftChild ;
    if(currRightChild->leftChild != Nil)
    {
        currRightChild->leftChild->Parent = Curr ;
    }

    currRightChild->Parent = Curr->Parent ;
    if(Curr->Parent == Nil)
    {
        Root = currRightChild ;
    }
    else
    {
        if(Curr == Curr->Parent->leftChild)
        {
            Curr->Parent->leftChild = currRightChild ;
        }
        else if(Curr == Curr->Parent->rightChild)
        {
            Curr->Parent->rightChild = currRightChild ;
        }
    }

    currRightChild->leftChild = Curr ;
    Curr->Parent = currRightChild ;

    return ;
}

void RedBlackTree::rightRotate(Node *Curr)
{
    Node *currLeftChild ;

    currLeftChild = Curr->leftChild;


    Curr->leftChild = currLeftChild->rightChild ;
    if(currLeftChild->rightChild != Nil)
    {
        currLeftChild->rightChild->Parent = Curr ;
    }

    currLeftChild->Parent = Curr->Parent ;
    if(Curr->Parent == Nil)
    {
        Root = currLeftChild ;
    }
    else
    {
        if(Curr == Curr->Parent->leftChild)
        {
            Curr->Parent->leftChild = currLeftChild ;
        }
        else if(Curr == Curr->Parent->rightChild)
        {
            Curr->Parent->rightChild = currLeftChild ;
        }
    }

    currLeftChild->rightChild = Curr ;
    Curr->Parent = currLeftChild ;

    return ;
}


void RedBlackTree::Insert(Node *newVal)
{
    Node *y, *x ;
    y = Nil ;
    x = Root ;

    while(x != Nil)
    {
        y = x ;
        if(newVal->Value >= x->Value)
        {
            x = x->rightChild ;
        }
        else
        {
            x = x->leftChild ;
        }
    }

    newVal->Parent = y ;

    if(y == Nil)
    {
        Root = newVal ;
        Root->Parent = Nil ;
    }
    else
    {
        if(newVal->Value >= y->Value)
        {
            y->rightChild = newVal ;
        }
        else
        {
            y->leftChild = newVal ;
        }
    }

    newVal->rightChild = Nil;
    newVal->leftChild = Nil ;
    newVal->Color = Red ;

    insertFixUp(newVal);
    return;
}


void RedBlackTree::insertFixUp(Node *newVal)
{
    Node *uncleNode, *fatherNode;

    while(newVal->Parent->Color == Red)
    {
        if(newVal->Parent == newVal->Parent->Parent->leftChild)
        {
            uncleNode = newVal->Parent->Parent->rightChild;
            fatherNode = newVal->Parent ;

            if(uncleNode->Color == Red)
            {
                uncleNode->Color = Black;
                fatherNode->Color = Black ;
                fatherNode->Parent->Color = Red ;
                newVal = fatherNode->Parent ;
            }
            else
            {
                if(newVal == fatherNode->rightChild)
                {
                    newVal = newVal->Parent ;
                    leftRotate(newVal);
                }
                else if(newVal == fatherNode->leftChild)
                {
                    fatherNode->Color = Black ;
                    fatherNode->Parent->Color = Red ;
                    rightRotate(fatherNode->Parent);
                }
            }
        }
        else if(newVal->Parent == newVal->Parent->Parent->rightChild)
        {
            uncleNode = newVal->Parent->Parent->leftChild;
            fatherNode = newVal->Parent ;

            if(uncleNode->Color == Red)
            {
                fatherNode->Color = Black ;
                uncleNode->Color = Black ;
                fatherNode->Parent->Color = Red ;
                newVal = fatherNode->Parent ;
            }
            else
            {
                if(newVal == fatherNode->leftChild)
                {
                    newVal = newVal->Parent ;
                    rightRotate(newVal) ;
                }
                else if(newVal == fatherNode->rightChild)
                {
                    fatherNode->Color = Black;
                    fatherNode->Parent->Color = Red ;
                    leftRotate(fatherNode->Parent);
                }
            }
        }
    }

    Root->Color = Black;
    return ;
}


int main()
{
    Nil = new Node(NilValue);


    /// ***** Do your Code Here***** ///

    RedBlackTree t ;
    ll a ;

    while(1)
    {
        ll c ;
        cout << "1. Insert \n2. Delete" << endl ;
        cin >> c >> a;
        Node *n ;
        n = new Node(a);
        if(c == 1)
        {
            t.Insert(n);
        }
        else if(c==2)
        {
            Node* p ;
            if(t.Root != Nil)
            {
                t.RBdelete(t.Search(a));
            }
            else
            {
                cout << "No item left"<<endl ;
            }
        }
        cout << "Success" << endl << endl  ;

        cout << "Asc Print: " ;
        t.AscPrint(t.Root);
        cout << endl ;

        cout << "Min: " <<  t.RBmin(t.Root)->Value << endl ;
        cout << "Max: " <<  t.RBmax(t.Root)->Value << endl ;
    }

    return 0 ;
}