#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <list>
#include <set>
#include <random>

using std::cin;
using std::cout;
using std::max;
using std::reverse;
using std::vector;
using std::pair;

template<class T>
struct RBTNode {
    RBTNode(T v, bool c = 0, RBTNode<T> *P = nullptr) {
        value = v;
        color = c;
        Left = Right = nullptr;
        Parent = P;
    }

    RBTNode<T> *Left;
    RBTNode<T> *Right;
    RBTNode<T> *Parent;
    T value;
    bool color;
};

template<class T>
class Iterator {
public:
    explicit Iterator(RBTNode<T> *tree) {
        current = tree;
    }

    Iterator<T> &operator=(const Iterator &other) {
        if (this != &other) {
            current = other.current;
        }
        return *this;
    }

    Iterator(const Iterator &other) {
        current = other.current;
    }

    bool operator!=(const Iterator &other) {
        return current != other.current;
    }

    bool operator==(const Iterator &other) {
        return current == other.current;
    }

    Iterator<T> &operator++() {
        if (current->Right) {
            current = current->Right;
            while (current->Left)
                current = current->Left;
        } else {
            while (current->Parent != nullptr && current->Parent->Right == current)
                current = current->Parent;
            current = current->Parent;
        }
        return *this;
    }

    Iterator<T> &operator--() {
        if (current->Left) {
            current = current->Left;
            while (current->Right)
                current = current->Right;
        } else {
            while (current->Parent->Left == current)
                current = current->Parent;
            current = current->Parent;
        }
        return *this;
    }

    Iterator<T> operator++(int such_a_rule) {
        Iterator<T> t = *this;
        if (current->Right) {
            current = current->Right;
            while (current->Left)
                current = current->Left;
        } else {
            while (current->Parent != nullptr && current->Parent->Right == current)
                current = current->Parent;
            if (current->Parent == nullptr) return Iterator(nullptr);
            current = current->Parent;
        }
        return t;
    }

    Iterator<T> operator--(int such_a_rule) {
        Iterator<T> t = *this;
        if (current->Left) {
            current = current->Left;
            while (current->Right)
                current = current->Right;
        } else {
            while (current->Parent != nullptr && current->Parent->Left == current)
                current = current->Parent;
            if (current->Parent == nullptr) return Iterator(nullptr);
            current = current->Parent;
        }
        return t;
    }

    T operator*() {
        return current->value;
    }

    RBTNode<T> *operator->() {
        return current;
    }

private:
    RBTNode<T> *current = nullptr;
};

template<class T>
class RBT {
    int size = 0;
public:
    typedef Iterator<T> iterator;

    Iterator<T> begin();

    Iterator<T> end();

    RBTNode<T> *Head;

    void insert(T v);

    RBTNode<T> *search(T v);

    void deleteVal(T v);

    bool Empty();

private:
    void RotateRight(RBTNode<T> *);

    void deleteNode(RBTNode<T> *v);

    void RotateLeft(RBTNode<T> *root);

    void ReColor(RBTNode<T> *node);

    void ReBalance(RBTNode<T> *root);

    void Insert(RBTNode<T> *root, T v);

    RBTNode<T> *MinReplacedVal(RBTNode<T> *x);

    RBTNode<T> *sibling(RBTNode<T> *node);

    void fixDoubleBlack(RBTNode<T> *x);
};

template<class T>
Iterator<T> RBT<T>::begin() {
    RBTNode<T> *t = Head;
    while (t->Left != nullptr) t = t->Left;
    return Iterator(t);
}

template<class T>
Iterator<T> RBT<T>::end() {
    RBTNode<T> *t = Head;
    while (t->Right != nullptr) t = t->Right;
    return Iterator(t);
}

template<class T>
void RBT<T>::RotateRight(RBTNode<T> *root) {
    if (root->Parent != nullptr) {
        if (root->Parent->Left != nullptr && root->Parent->Left == root)
            root->Parent->Left = root->Left;
        else
            root->Parent->Right = root->Left;
    }

    root->Left->Parent = root->Parent;
    root->Parent = root->Left;
    root->Left = root->Parent->Right;
    if (root->Parent->Right != nullptr) root->Parent->Right->Parent = root;
    if (root->Parent->Parent == nullptr) Head = root->Parent;
    root->Parent->Right = root;
}

template<class T>
void RBT<T>::RotateLeft(RBTNode<T> *root) {
    if (root->Parent != nullptr) {
        if (root->Parent->Left != nullptr && root->Parent->Left == root)
            root->Parent->Left = root->Right;
        else
            root->Parent->Right = root->Right;
    }
    root->Right->Parent = root->Parent;
    root->Parent = root->Right;
    root->Right = root->Parent->Left;
    if (root->Parent->Left != nullptr) root->Parent->Left->Parent = root;
    if (root->Parent->Parent == nullptr) Head = root->Parent;
    root->Parent->Left = root;
}

template<class T>
void RBT<T>::ReColor(RBTNode<T> *node) {
    if (node->Parent->Parent->Right != nullptr) node->Parent->Parent->Right->color = 0;
    if (node->Parent->Parent->Left != nullptr) node->Parent->Parent->Left->color = 0;
    if (node->Parent->Parent->Parent == nullptr) node->Parent->Parent->color = 0;
    else
        node->Parent->Parent->color = 1;
}

template<class T>
void RBT<T>::ReBalance(RBTNode<T> *root) {
    if (root->Parent == nullptr || root->Parent->color == 0) return;

    if (root->Parent->Left == root && root->Parent->Parent->Left == root->Parent) {
        if (root->Parent->Parent->Right == nullptr || root->Parent->Parent->Right->color == 0) {
            RotateRight(root->Parent->Parent);
            root->Parent->color = 0;
            root->Parent->Right->color = 1;
        } else {
            ReColor(root);
            ReBalance(root->Parent->Parent);
        }
    } else if (root->Parent->Right == root && root->Parent->Parent->Left == root->Parent) {
        if (root->Parent->Parent->Right == nullptr || root->Parent->Parent->Right->color == 0) {
            RotateLeft(root->Parent);
            RotateRight(root->Parent);
            root->color = 0;
            root->Right->color = 1;
        } else {
            ReColor(root);
            ReBalance(root->Parent->Parent);
        }
    } else if (root->Parent->Right == root && root->Parent->Parent->Right == root->Parent) {
        if (root->Parent->Parent->Left == nullptr || root->Parent->Parent->Left->color == 0) {
            RotateLeft(root->Parent->Parent);
            root->Parent->color = 0;
            root->Parent->Left->color = 1;
        } else {
            ReColor(root);
            ReBalance(root->Parent->Parent);
        }
    } else if (root->Parent->Left == root && root->Parent->Parent->Right == root->Parent) {
        if (root->Parent->Parent->Left == nullptr ||
            root->Parent->Parent->Left->color == 0) {
            RotateRight(root->Parent);
            RotateLeft(root->Parent);
            root->color = 0;
            root->Left->color = 1;
        } else {
            ReColor(root);
            ReBalance(root->Parent->Parent);
        }
    }
}

template<class T>
void RBT<T>::Insert(RBTNode<T> *root, T v) {
    RBTNode<T> *P = nullptr;
    while (root != nullptr) {
        P = root;
        if (root->value < v)
            root = root->Right;
        else
            root = root->Left;
    }

    root = new RBTNode<T>(v, 1, P);
    if (P->value >= root->value) P->Left = root;
    else
        P->Right = root;
    ReBalance(root);
}

template<class T>
RBTNode<T> *RBT<T>::MinReplacedVal(RBTNode<T> *x) {

    if (x->Left != nullptr and x->Right != nullptr) {
        RBTNode<T> *temp_variable = x->Right;
        while (temp_variable->Left != nullptr)
            temp_variable = temp_variable->Left;
        return temp_variable;
    }

    if (x->Left == nullptr and x->Right == nullptr)
        return nullptr;

    if (x->Left != nullptr)
        return x->Left;
    else
        return x->Right;
}

template<class T>
RBTNode<T> *RBT<T>::sibling(RBTNode<T> *node) {
    if (node->Parent == nullptr)
        return nullptr;

    if (node == node->Parent->Left)
        return node->Parent->Right;

    return node->Parent->Left;
}

template<class T>
void RBT<T>::fixDoubleBlack(RBTNode<T> *x) {
    if (x == Head)
        return;

    RBTNode<T> *sib = sibling(x), *parent = x->Parent;
    if (sib == nullptr)
        fixDoubleBlack(parent);
    else {
        if (sib->color == 1) {
            parent->color = 1;
            sib->color = 0;

            if (sib->Parent->Left == sib)
                RotateRight(parent);
            else
                RotateLeft(parent);

            fixDoubleBlack(x);
        } else {
            if ((sib->Left != nullptr && sib->Left->color == 1) ||
                (sib->Right != nullptr && sib->Right->color == 1)) {

                if (sib->Left != nullptr && sib->Left->color == 1) {
                    if (sib->Parent->Left == sib) {
                        sib->Left->color = sib->color;
                        sib->color = parent->color;
                        RotateRight(parent);
                    } else {
                        sib->Left->color = parent->color;
                        RotateRight(sib);
                        RotateLeft(parent);
                    }
                } else {
                    if (sib->Parent->Left == sib) {
                        sib->Right->color = parent->color;
                        RotateLeft(sib);
                        RotateRight(parent);
                    } else {
                        sib->Right->color = sib->color;
                        sib->color = parent->color;
                        RotateLeft(parent);
                    }
                }
                parent->color = 0;
            } else {
                sib->color = 1;
                if (parent->color == 0)
                    fixDoubleBlack(parent);
                else
                    parent->color = 0;
            }
        }
    }
}

template<class T>
void RBT<T>::deleteNode(RBTNode<T> *v) {
    RBTNode<T> *u = MinReplacedVal(v);

    bool bb = ((u == nullptr or u->color == 0) and (v->color == 0));
    RBTNode<T> *parent = v->Parent;

    if (u == nullptr) {
        if (v == Head) {
            Head = nullptr;
        } else {
            if (bb)
                fixDoubleBlack(v);
            else {
                RBTNode<T> *t = sibling(v);
                if (t != nullptr)
                    t->color = 1;
            }

            if (v->Parent->Left == v)
                parent->Left = nullptr;
            else
                parent->Right = nullptr;
        }
        delete v;
        return;
    }

    if (v->Left == nullptr or v->Right == nullptr) {
        if (v == Head) {
            v->value = u->value;
            v->Left = v->Right = nullptr;
            delete u;
        } else {
            if (v->Parent->Left == v)
                parent->Left = u;
            else
                parent->Right = u;

            delete v;
            u->Parent = parent;

            if (bb)
                fixDoubleBlack(u);
            else
                u->color = 0;
        }
        return;
    }

    T temp_variable;
    temp_variable = u->value;
    u->value = v->value;
    v->value = temp_variable;

    deleteNode(u);
}

template<class T>
RBTNode<T> *RBT<T>::search(T v) {
    if (Head == nullptr) return nullptr;
    RBTNode<T> *root = Head;
    while (root != nullptr) {
        if (root->value > v)
            root = root->Left;
        else if (root->value < v) root = root->Right;
        else if (root->value == v)
            return root;
    }
    return nullptr;
}

template<class T>
void RBT<T>::deleteVal(T v) {
    auto t = search(v);
    if (t == nullptr) return;
    deleteNode(t);
    --size;
}


template<class T>
void RBT<T>::insert(T v) {
    if (Head == nullptr) Head = new RBTNode<T>(v);
    else
        Insert(Head, v);
    ++size;
}

template<class T>
bool RBT<T>::Empty() {
    return size == 0;
}

int main() {
    auto tree = new RBT<int64_t>();
    tree->insert(25);
    cout << (tree->search(25) != nullptr) << '\n';
    tree->insert(36);
    tree->deleteVal(25);
    cout << *tree->begin();
}