#include <iostream>

template<typename Key, typename T>
class Map{
public:
    typedef Key key_type;
    typedef T map_type;
    typedef std::pair<Key,T> value_type;

    enum Color{
        RED,BLACK
    };

    struct Node{
        Color color;
        Node* prev;
        Node* next;
        Node* parent;
        Node* left;
        Node* right;

        value_type val;

        Node():prev(nullptr),next(nullptr),left(nullptr),right(nullptr),parent(nullptr),color(RED){}
        Node(value_type val_):Node(), val(val_){}
    };
    class iterator{
    public:
        Node* ptr;

        iterator() = delete;
        iterator(Node* ptr_):ptr(ptr_){}
        iterator(const iterator& it_){
            if(&this == it_)
                return;
            ptr = new Node(*(it_.ptr));
        }
        iterator& operator++(){
            ptr = ptr->next;
            return *this;
        }
        iterator operator++(int){
            iterator tmp = *this;
            operator++();
            return tmp;
        }
        iterator& operator--(){
            ptr = ptr->prev;
            return *this;
        }
        iterator operator--(int){
            iterator tmp = *this;
            operator--();
            return tmp;
        }
        value_type& operator*() const{
            return ptr->val;
        }
        Node* operator->() const{
            return ptr;
        }
        bool operator==(const iterator& rhs) const{
            return (ptr == rhs.ptr);
        }
        bool operator!=(const iterator& rhs) const{
            return !(*this == rhs);
        }
    };
    iterator begin(){
        return head->next;
    }
    iterator end(){
        return tail;
    }

    std::pair<iterator,bool> insert(const value_type& v){
        Node* newNode = new Node(v);
        std::pair<iterator,bool> p = _recursive_insert_(root,newNode);
        if(!p.second){
            delete newNode;
        }else {
            _repair_tree_(newNode);
            root = newNode;
            while (get_parent(root) != nullptr)
                root = get_parent(root);
        }
        return p;
    }

private:
    Node* root;
    Node* head;
    Node* tail;

    Node* get_parent(Node* current){
        return (current->parent == nullptr ? nullptr : current->parent);
    }
    Node* get_most_right_node(Node* current){
        return(current->right == nullptr ? current : get_most_right_node(current->right));
    }
    Node* get_most_left_node(Node* current){
        return(current->left == nullptr ? current : get_most_left_node(current->right));
    }



    std::pair<iterator,bool> _recursive_insert_(Node* place, Node* who){
        if(place->val.first == who->val.first)
            return std::make_pair(iterator(place),false);
        if(place->val.first > who->val.first){
            if(place->left == nullptr) {
                place->left = who;
                who->parent = place;
            }else {
                 return _recursive_insert_(place->left, who);
            }
        }
        else{
            if(place->right == nullptr) {
                place->right = who;
                who->parent = place;
            }else {
                return _recursive_insert_(place->right, who);
            }
        }
        who->color = RED;
        who->parent = get_parent(who);
        who->left = nullptr;
        who->right = nullptr;
        if(place->val.first > who->val.first){
            who->next = place;
            who->prev = get_most_right_node();
        }


    }
};


int main(){
    return 0;
};