// tree internal header

#if     _MSC_VER > 1000 /*IFSTRIP=IGN*/
#pragma once
#endif

#ifndef _XTREE_
#define _XTREE_
#include <cstddef>
#include <iterator>
#include <memory>
#include <xutility>

#ifdef  _MSC_VER
#pragma pack(push,8)
#endif  /* _MSC_VER */
_STD_BEGIN
                // TEMPLATE CLASS _Tree
template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
        class _Tree {
protected:
        enum _Redbl {_Red, _Black};
        struct _Node;
        friend struct _Node;
        typedef _POINTER_X(_Node, _A) _Nodeptr;
        struct _Node {
                _Nodeptr _Left, _Parent, _Right;
                _Ty _Value;
                _Redbl _Color;
                };
        typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
        typedef _REFERENCE_X(const _K, _A) _Keyref;
        typedef _REFERENCE_X(_Redbl, _A) _Rbref;
        typedef _REFERENCE_X(_Ty, _A) _Vref;
        static _Rbref _Color(_Nodeptr _P)
                {return ((_Rbref)(*_P)._Color); }
        static _Keyref _Key(_Nodeptr _P)
                {return (_Kfn()(_Value(_P))); }
        static _Nodepref _Left(_Nodeptr _P)
                {return ((_Nodepref)(*_P)._Left); }
        static _Nodepref _Parent(_Nodeptr _P)
                {return ((_Nodepref)(*_P)._Parent); }
        static _Nodepref _Right(_Nodeptr _P)
                {return ((_Nodepref)(*_P)._Right); }
        static _Vref _Value(_Nodeptr _P)
                {return ((_Vref)(*_P)._Value); }
public:
        typedef _Tree<_K, _Ty, _Kfn, _Pr, _A> _Myt;
        typedef _K key_type;
        typedef _Ty value_type;
        typedef _A::size_type size_type;
        typedef _A::difference_type difference_type;
        typedef _POINTER_X(_Ty, _A) _Tptr;
        typedef _POINTER_X(const _Ty, _A) _Ctptr;
        typedef _REFERENCE_X(_Ty, _A) reference;
        typedef _REFERENCE_X(const _Ty, _A) const_reference;
                // CLASS const_iterator
        class iterator;
        class const_iterator;
        friend class const_iterator;
        class const_iterator : public _Bidit<_Ty, difference_type> {
        public:
                const_iterator()
                        {}
                const_iterator(_Nodeptr _P)
                        : _Ptr(_P) {}
                const_iterator(const iterator& _X)
                        : _Ptr(_X._Ptr) {}
                const_reference operator*() const
                        {return (_Value(_Ptr)); }
                _Ctptr operator->() const
                        {return (&**this); }
                const_iterator& operator++()
                        {_Inc();
                        return (*this); }
                const_iterator operator++(int)
                        {const_iterator _Tmp = *this;
                        ++*this;
                        return (_Tmp); }
                const_iterator& operator--()
                        {_Dec();
                        return (*this); }
                const_iterator operator--(int)
                        {const_iterator _Tmp = *this;
                        --*this;
                        return (_Tmp); }
                bool operator==(const const_iterator& _X) const
                        {return (_Ptr == _X._Ptr); }
                bool operator!=(const const_iterator& _X) const
                        {return (!(*this == _X)); }
                void _Dec()
                        {_Lockit _Lk;
                        if (_Color(_Ptr) == _Red
                                && _Parent(_Parent(_Ptr)) == _Ptr)
                                _Ptr = _Right(_Ptr);
                        else if (_Left(_Ptr) != _Nil)
                                _Ptr = _Max(_Left(_Ptr));
                        else
                                {_Nodeptr _P;
                                while (_Ptr == _Left(_P = _Parent(_Ptr)))
                                        _Ptr = _P;
                                _Ptr = _P; }}
                void _Inc()
                        {_Lockit _Lk;
                        if (_Right(_Ptr) != _Nil)
                                _Ptr = _Min(_Right(_Ptr));
                        else
                                {_Nodeptr _P;
                                while (_Ptr == _Right(_P = _Parent(_Ptr)))
                                        _Ptr = _P;
                                if (_Right(_Ptr) != _P)
                                        _Ptr = _P; }}
                _Nodeptr _Mynode() const
                        {return (_Ptr); }
        protected:
                _Nodeptr _Ptr;
                };
                // CLASS iterator
        friend class iterator;
        class iterator : public const_iterator {
        public:
                iterator()
                        {}
                iterator(_Nodeptr _P)
                        : const_iterator(_P) {}
                reference operator*() const
                        {return (_Value(_Ptr)); }
                _Tptr operator->() const
                        {return (&**this); }
                iterator& operator++()
                        {_Inc();
                        return (*this); }
                iterator operator++(int)
                        {iterator _Tmp = *this;
                        ++*this;
                        return (_Tmp); }
                iterator& operator--()
                        {_Dec();
                        return (*this); }
                iterator operator--(int)
                        {iterator _Tmp = *this;
                        --*this;
                        return (_Tmp); }
                bool operator==(const iterator& _X) const
                        {return (_Ptr == _X._Ptr); }
                bool operator!=(const iterator& _X) const
                        {return (!(*this == _X)); }
                };
        typedef reverse_bidirectional_iterator<iterator,
                value_type, reference, _Tptr, difference_type>
                        reverse_iterator;
        typedef reverse_bidirectional_iterator<const_iterator,
                value_type, const_reference, _Ctptr, difference_type>
                        const_reverse_iterator;
        typedef pair<iterator, bool> _Pairib;
        typedef pair<iterator, iterator> _Pairii;
        typedef pair<const_iterator, const_iterator> _Paircc;
        explicit _Tree(const _Pr& _Parg, bool _Marg = true,
                const _A& _Al = _A())
                : allocator(_Al),
                key_compare(_Parg), _Multi(_Marg)
                {_Init(); }
        _Tree(const _Ty *_F, const _Ty *_L,
                const _Pr& _Parg, bool _Marg = true,
                const _A& _Al = _A())
                : allocator(_Al),
                key_compare(_Parg), _Multi(_Marg)
                {_Init();
                insert(_F, _L); }
        _Tree(const _Myt& _X)
                : allocator(_X.allocator),
                key_compare(_X.key_compare), _Multi(_X._Multi)
                {_Init();
                _Copy(_X); }
        ~_Tree()
                {erase(begin(), end());
                _Freenode(_Head);
                _Head = 0, _Size = 0;
                        {_Lockit _Lk;
                        if (--_Nilrefs == 0)
                                {_Freenode(_Nil);
                                _Nil = 0; }}}
        _Myt& operator=(const _Myt& _X)
                {if (this != &_X)
                        {erase(begin(), end());
                        key_compare = _X.key_compare;
                        _Copy(_X); }
                return (*this); }
        iterator begin()
                {return (iterator(_Lmost())); }
        const_iterator begin() const
                {return (const_iterator(_Lmost())); }
        iterator end()
                {return (iterator(_Head)); }
        const_iterator end() const
                {return (const_iterator(_Head)); }
        reverse_iterator rbegin()
                {return (reverse_iterator(end())); }
        const_reverse_iterator rbegin() const
                {return (const_reverse_iterator(end())); }
        reverse_iterator rend()
                {return (reverse_iterator(begin())); }
        const_reverse_iterator rend() const
                {return (const_reverse_iterator(begin())); }
        size_type size() const
                {return (_Size); }
        size_type max_size() const
                {return (allocator.max_size()); }
        bool empty() const
                {return (size() == 0); }
        _A get_allocator() const
                {return (allocator); }
        _Pr key_comp() const
                {return (key_compare); }
        _Pairib insert(const value_type& _V)
                {_Nodeptr _X = _Root();
                _Nodeptr _Y = _Head;
                bool _Ans = true;
                { _Lockit Lk;
                        while (_X != _Nil)
                                {_Y = _X;
                                _Ans = key_compare(_Kfn()(_V), _Key(_X));
                                _X = _Ans ? _Left(_X) : _Right(_X); }
                }
                if (_Multi)
                        return (_Pairib(_Insert(_X, _Y, _V), true));
                iterator _P = iterator(_Y);
                if (!_Ans)
                        ;
                else if (_P == begin())
                        return (_Pairib(_Insert(_X, _Y, _V), true));
                else
                        --_P;
                if (key_compare(_Key(_P._Mynode()), _Kfn()(_V)))
                        return (_Pairib(_Insert(_X, _Y, _V), true));
                return (_Pairib(_P, false)); }
        iterator insert(iterator _P, const value_type& _V)
                {if (size() == 0)
                        ;
                else if (_P == begin())
                        {if (key_compare(_Kfn()(_V), _Key(_P._Mynode())))
                                return (_Insert(_Head, _P._Mynode(), _V)); }
                else if (_P == end())
                        {_Lockit Lk;
                        if (key_compare(_Key(_Rmost()), _Kfn()(_V)))
                                return (_Insert(_Nil, _Rmost(), _V)); }
                else
                        {iterator _Pb = _P;
                        if (key_compare(_Key((--_Pb)._Mynode()), _Kfn()(_V))
                                && key_compare(_Kfn()(_V), _Key(_P._Mynode())))
                                {_Lockit _Lk;
                                if (_Right(_Pb._Mynode()) == _Nil)
                                        return (_Insert(_Nil, _Pb._Mynode(), _V));
                                else
                                        return (_Insert(_Head, _P._Mynode(), _V)); }}
                return (insert(_V).first); }
        void insert(iterator _F, iterator _L)
                {for (; _F != _L; ++_F)
                        insert(*_F); }
        void insert(const value_type *_F, const value_type *_L)
                {for (; _F != _L; ++_F)
                        insert(*_F); }
        iterator erase(iterator _P)
                {_Nodeptr _X;
                _Nodeptr _Y = (_P++)._Mynode();
                _Nodeptr _Z = _Y;
                _Lockit _Lk;
                if (_Left(_Y) == _Nil)
                        _X = _Right(_Y);
                else if (_Right(_Y) == _Nil)
                        _X = _Left(_Y);
                else
                        _Y = _Min(_Right(_Y)), _X = _Right(_Y);
                if (_Y != _Z)
                        {_Parent(_Left(_Z)) = _Y;
                        _Left(_Y) = _Left(_Z);
                        if (_Y == _Right(_Z))
                                _Parent(_X) = _Y;
                        else
                                {_Parent(_X) = _Parent(_Y);
                                _Left(_Parent(_Y)) = _X;
                                _Right(_Y) = _Right(_Z);
                                _Parent(_Right(_Z)) = _Y; }
                        if (_Root() == _Z)
                                _Root() = _Y;
                        else if (_Left(_Parent(_Z)) == _Z)
                                _Left(_Parent(_Z)) = _Y;
                        else
                                _Right(_Parent(_Z)) = _Y;
                        _Parent(_Y) = _Parent(_Z);
                        std::swap(_Color(_Y), _Color(_Z));
                        _Y = _Z; }
                else
                        {_Parent(_X) = _Parent(_Y);
                        if (_Root() == _Z)
                                _Root() = _X;
                        else if (_Left(_Parent(_Z)) == _Z)
                                _Left(_Parent(_Z)) = _X;
                        else
                                _Right(_Parent(_Z)) = _X;
                        if (_Lmost() != _Z)
                                ;
                        else if (_Right(_Z) == _Nil)
                                _Lmost() = _Parent(_Z);
                        else
                                _Lmost() = _Min(_X);
                        if (_Rmost() != _Z)
                                ;
                        else if (_Left(_Z) == _Nil)
                                _Rmost() = _Parent(_Z);
                        else
                                _Rmost() = _Max(_X); }
                if (_Color(_Y) == _Black)
                        {while (_X != _Root() && _Color(_X) == _Black)
                                if (_X == _Left(_Parent(_X)))
                                        {_Nodeptr _W = _Right(_Parent(_X));
                                        if (_Color(_W) == _Red)
                                                {_Color(_W) = _Black;
                                                _Color(_Parent(_X)) = _Red;
                                                _Lrotate(_Parent(_X));
                                                _W = _Right(_Parent(_X)); }
                                        if (_Color(_Left(_W)) == _Black
                                                && _Color(_Right(_W)) == _Black)
                                                {_Color(_W) = _Red;
                                                _X = _Parent(_X); }
                                        else
                                                {if (_Color(_Right(_W)) == _Black)
                                                        {_Color(_Left(_W)) = _Black;
                                                        _Color(_W) = _Red;
                                                        _Rrotate(_W);
                                                        _W = _Right(_Parent(_X)); }
                                                _Color(_W) = _Color(_Parent(_X));
                                                _Color(_Parent(_X)) = _Black;
                                                _Color(_Right(_W)) = _Black;
                                                _Lrotate(_Parent(_X));