namespace meow{
  template<class Key, class Value>
  inline SplayTree<Key, Value>::Node::Node(Key   const& __key,
                                           Value const& __value):
  _key(__key),
  _keyOffset(0),
  _value(__value),
  _size(1),
  _parent(NULL),
  _lChild(NULL),
  _rChild(NULL){ }
  //
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::offsetAdd(Node* __node, Key const& __delta) const{
    __node->_key       = __node->_key       + __delta;
    __node->_keyOffset = __node->_keyOffset + __delta;
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::sizeUpdate(Node* __node) const{
    if(__node != NULL){
      __node->_size = 1;
      if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size;
      if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size;
    }
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::offsetDown(Node* __node) const{
    if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset);
    if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset);
    __node->_keyOffset = 0;
  }
  //
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::connectLChild(Node* __parent, Node* __child) const{
    if(__parent != NULL) __parent->_lChild = __child;
    if(__child  != NULL) __child ->_parent = __parent;
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::connectRChild(Node* __parent, Node* __child) const{
    if(__parent != NULL) __parent->_rChild = __child;
    if(__child  != NULL) __child ->_parent = __parent;
  }
  //
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::clear(Node* __node){
    if(__node != NULL){
      clear(__node->_lChild);
      clear(__node->_rChild);
      delete __node;
    }
    return NULL;
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::dup(Node* __node){
    if(__node == NULL) return NULL;
    offsetDown(__node);
    Node* node = new Node(__node->_key, __node->_value);
    connectLChild(node, dup(__node->_lChild));
    connectRChild(node, dup(__node->_rChild));
    sizeUpdate(node);
    return node;
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node const*
  SplayTree<Key, Value>::setRoot(Node* __node) const{
    connectLChild(NULL, (((SplayTree*)this)->_root = __node));
    return _root;
  }
  //
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::rotate(Node* __parent, Node* __child) const{
    if(__parent->_lChild == __child){
      connectLChild(__parent, __child->_rChild);
      connectRChild(__child , __parent);
    }else{
      connectRChild(__parent, __child->_lChild);
      connectLChild(__child , __parent);
    }
    sizeUpdate(__parent);
    sizeUpdate(__child );
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::rotate(Node* __grand,
                                Node* __parent,
                                Node* __child) const{
    if(__grand->_lChild == __parent){
      if(__parent->_lChild == __child){
        connectLChild(__grand , __parent->_rChild);
        connectLChild(__parent, __child ->_rChild);
        connectRChild(__child , __parent);
        connectRChild(__parent, __grand );
      }else{
        connectRChild(__parent, __child->_lChild);
        connectLChild(__grand , __child->_rChild);
        connectLChild(__child, __parent);
        connectRChild(__child, __grand );
      }
    }else if(__grand->_rChild == __parent){
      if(__parent->_rChild == __child){
        connectRChild(__grand , __parent->_lChild);
        connectRChild(__parent, __child ->_lChild);
        connectLChild(__child , __parent);
        connectLChild(__parent, __grand );
      }else{
        connectRChild(__grand , __child->_lChild);
        connectLChild(__parent, __child->_rChild);
        connectLChild(__child, __grand );
        connectRChild(__child, __parent);
      }
    }
    sizeUpdate(__grand );
    sizeUpdate(__parent);
    sizeUpdate(__child );
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::splay(Node* __node) const{
    if(__node == NULL) return NULL;
    for(Node *parent, *grand, *child = __node; child->_parent != NULL; ){
      parent = child ->_parent;
      grand  = parent->_parent;
      if(grand == NULL){
        rotate(parent, child);
        break;
      }else{
        Node* g_grand = grand->_parent;
        rotate(grand, parent, child);
        if(g_grand == NULL) break;
        if(g_grand->_lChild == grand) connectLChild(g_grand, child);
        else                          connectRChild(g_grand, child);
      }
    }
    sizeUpdate(__node);
    return __node;
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::findKey(Node* __node, Key const& __key) const{
    Node* ret = __node;
    while(__node != NULL){
      offsetDown(__node);
      ret = __node;
      if(!(__key < __node->_key)){
        if(!(__node->_key< __key)) break;
        __node = __node->_rChild;
      }else{
        __node = __node->_lChild;
      }
    }
    return ret;
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::findMinMax(Node* __node, bool minimum) const{
    Node* ret = __node;
    while(__node != NULL){
      offsetDown(__node);
      ret = __node;
      __node = (minimum ? __node->_lChild : __node->_rChild);
    }
    return ret;
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::findOrder(Node* __node, size_t __order) const{
    Node* ret = __node;
    while(__node != NULL){
      offsetDown(__node);
      ret = __node;
      size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size);
      if     (ord == __order) return ret;
      else if(ord <  __order){ __node = __node->_rChild; __order -= ord; }
      else                   { __node = __node->_lChild;                 }
    }
    return ret;
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::split(Node* __root, Node** __left, Node** __right){
    if(__root == NULL){ *__left  = NULL; *__right = NULL; return ; }
    offsetDown(__root);
    *__left  = __root;
    *__right = __root->_rChild;
    if(*__right != NULL){
      (*__left )->_rChild = NULL;
      (*__right)->_parent = NULL;
      sizeUpdate(*__left);
    }
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Node*
  SplayTree<Key, Value>::merge(Node* __left, Node* __right){
    if(__left  == NULL) return __right;
    if(__right == NULL) return __left ;
    offsetDown(__left);
    connectRChild(__left, __right);
    sizeUpdate(__left);
    return __left;
  }
  template<class Key, class Value>
  inline void SplayTree<Key, Value>::print(Node* __now, int __depth) const{
    if(__now == NULL) return ;
    printf("%*s [%llX]:(%lu)\tParent=%llX Left=%llX Right=%llX\n",
           __depth * 2, "",
           (long long unsigned)__now,
           __now->_size,
           (long long unsigned)__now->_parent,
           (long long unsigned)__now->_lChild,
           (long long unsigned)__now->_rChild);
    print(__now->_lChild, __depth + 1);
    print(__now->_rChild, __depth + 1);
  }
  //
  template<class Key, class Value>
  inline void SplayTree<Key, Value>::Element::reset(Node* __node){
    _node = __node;
    delete _entry;
    if(__node == NULL) _entry = NULL;
    else               _entry = new Entry(__node->_key, __node->_value);
  }
  template<class Key, class Value>
  inline SplayTree<Key, Value>::Element::Element():
  _entry(NULL), _node(NULL){ }
  template<class Key, class Value>
  inline SplayTree<Key, Value>::Element::Element(Node* __node):
  _entry(NULL), _node(NULL){ reset(__node); }
  template<class Key, class Value>
  inline SplayTree<Key, Value>::Element::Element(Element const& __element2):
  _entry(NULL), _node(NULL){ reset(__element2._node); }
  template<class Key, class Value>
  inline SplayTree<Key, Value>::Element::~Element(){ delete _entry; }
  //
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element&
  SplayTree<Key, Value>::Element::operator=(Element const& __e2){
    reset(__e2._node);
    return *this;
  }
  //
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element::Entry*
  SplayTree<Key, Value>::Element::operator->(){ return  _entry; }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element::Entry&
  SplayTree<Key, Value>::Element::operator*(){ return *_entry; }
  //
  template<class Key, class Value>
  inline bool
  SplayTree<Key, Value>::Element::operator==(Element const& __e2) const{
    return (_node == __e2._node);
  }
  template<class Key, class Value>
  inline bool
  SplayTree<Key, Value>::Element::operator!=(Element const& __e2) const{
    return (_node != __e2._node);
  }
  //
  template<class Key, class Value>
  inline SplayTree<Key, Value>::SplayTree(): _root(NULL){ }
  template<class Key, class Value>
  inline SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2):
  _root(NULL){ setRoot(dup(__tree2._root)); }
  template<class Key, class Value>
  inline SplayTree<Key, Value>::~SplayTree(){ clear(_root); }
  template<class Key, class Value>
  inline SplayTree<Key, Value>&
  SplayTree<Key, Value>::operator=(SplayTree const& __tree2){
    clear(_root);
    setRoot(dup(__tree2._root));
    return *this;
  }
  //
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::lowerBound(Key const& __key) const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findKey(me->_root, __key)));
    if(_root == NULL || !(_root->_key < __key)) return Element(_root);
    if(_root->_rChild == NULL)                  return Element(NULL);
    setRoot(splay(findMinMax(me->_root->_rChild, true)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::upperBound(Key const& __key) const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findKey(me->_root, __key)));
    if(_root == NULL || __key < _root->_key) return Element(_root);
    if(_root->_rChild == NULL) return Element(NULL);
    setRoot(splay(findMinMax(me->_root->_rChild, true)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findKey(me->_root, __key)));
    if(_root == NULL || !(__key < _root->_key)) return Element(_root);
    if(_root->_lChild == NULL){
      return NULL;
    }
    setRoot(splay(findMinMax(me->_root->_lChild, false)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findKey(me->_root, __key)));
    if(_root == NULL || _root->_key < __key) return Element(_root);
    if(_root->_lChild == NULL)               return Element(NULL);
    setRoot(splay(findMinMax(me->_root->_lChild, false)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::find(Key const& __key) const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findKey(me->_root, __key)));
    if(_root != NULL && _root->_key == __key) return Element(_root);
    return Element(NULL);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::order(size_t __order) const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findOrder(me->_root, __order + 1)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::first() const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findMinMax(me->_root, true)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::last() const{
    SplayTree* me = (SplayTree*)this;
    setRoot(splay(findMinMax(me->_root, false)));
    return Element(_root);
  }
  template<class Key, class Value>
  inline typename SplayTree<Key, Value>::Element
  SplayTree<Key, Value>::end() const{ return Element(NULL); }
  template<class Key, class Value>
  inline size_t SplayTree<Key, Value>::size() const{
    return (_root == NULL ? 0 : _root->_size);
  }
  template<class Key, class Value>
  inline bool SplayTree<Key, Value>::empty() const{ return (size() == 0); }
  //
  template<class Key, class Value>
  inline void SplayTree<Key, Value>::clear(){
    clear(_root);
    _root = NULL;
  }
  template<class Key, class Value>
  inline void SplayTree<Key, Value>::keyOffset(Key const& __delta){
    if(_root != NULL){
      offsetAdd(_root, __delta);
    }
  }
  template<class Key, class Value>
  inline bool SplayTree<Key, Value>::insert(Key const& __key,
                                            Value const& __value){
    if(_root == NULL){
      setRoot(new Node(__key, __value));
      return true;
    }
    Node* parent = findKey(_root, __key);
    Node* new_node;
    if(parent->_key < __key){
      connectRChild(parent, new_node = new Node(__key, __value));
      sizeUpdate(parent);
    }else if(__key < parent->_key){
      connectLChild(parent, new_node = new Node(__key, __value));
      sizeUpdate(parent);
    }else{
      setRoot(splay(parent));
      return false;
    }
    setRoot(splay(new_node));
    return true;
  }
  template<class Key, class Value>
  inline bool SplayTree<Key, Value>::erase(Key const& __key){
    if(_root == NULL) return false;
    Node* body = findKey(_root, __key);
    if(body->_key < __key || __key < body->_key){
      setRoot(splay(body));
      return false;
    }
    Node* ghost;
    if(body->_rChild == NULL){
      ghost = body->_lChild;
      if(ghost != NULL) offsetDown(ghost);
    }else{
      ghost = findMinMax(body->_rChild, true);
      connectLChild(ghost, body->_lChild);
      if(ghost != body->_rChild){
        connectLChild(ghost->_parent, ghost->_rChild);
        connectRChild(ghost, body->_rChild);
        for(Node* acestor = ghost->_parent;
            acestor != ghost;
            acestor = acestor->_parent){
          sizeUpdate(acestor);
        }
      }
      sizeUpdate(ghost);
    }
    if(body->_parent != NULL && body->_parent->_lChild == body){
      connectLChild(body->_parent, ghost);
    }else{
      connectRChild(body->_parent, ghost);
    }
    setRoot(splay(ghost != NULL ? ghost : body->_parent));
    return true;
  }
  template<class Key, class Value>
  inline Value&
  SplayTree<Key, Value>::operator[](Key const& __key){
    if(find(__key) == end()) insert(__key, Value());
    return find(__key)->second;
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::splitOut(Key const& __upper_bound, SplayTree* __right){
    __right->clear();
    if(rLowerBound(__upper_bound) != Element(NULL)){
      split(_root, &_root, &(__right->_root));
    }else{
      __right->_root = _root;
      _root = NULL;
    }
  }
  template<class Key, class Value>
  inline bool
  SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
    if(_root == NULL || __tree2->_root == NULL ||
       last()->first < __tree2->first()->first){
      setRoot(merge(_root, __tree2->_root));
      __tree2->_root = NULL;
      return true;
    }
    return false;
  }
  template<class Key, class Value>
  inline bool
  SplayTree<Key, Value>::merge(SplayTree* __tree2){
    if(_root == NULL || __tree2->_root == NULL){
      setRoot(merge(_root, __tree2->_root));
    }else{
      if(last()->first < __tree2->first()->first){
        setRoot(merge(_root, __tree2->_root));
      }else if(__tree2->last()->first < first()->first){
        setRoot(merge(__tree2->_root, _root));
      }else{
        return false;
      }
    }
    __tree2->_root = NULL;
    return true;
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::print() const{
    print(_root, 0);
  }
  template<class Key, class Value>
  inline void
  SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
    __tree2->clear();
    __tree2->_root = _root;
    _root = NULL;
  }
}