import enum

class entry_not_found(Exception):
   
   pass

class entry_already_exists(Exception):
   
   pass

class state(enum.Enum):
   header = 0
   left_high = 1
   right_high = 2
   balanced = 3

class direction(enum.Enum):
   from_left = 0
   from_right = 1

from abc import ABC, abstractmethod

class comparer(ABC):

    @abstractmethod
    def compare(self,t):
        pass

class node(comparer):

    def __init__(self):
        self.parent = None
        self.left = self
        self.right = self
        self.balance = state.header

    def compare(self,t):
        if self.key < t:
             return -1
        elif t < self.key:
             return 1
        else:
             return 0

    def is_header(self):
        return self.balance == state.header

    def length(self):
        if self != None:
           if self.left != None:
              left = self.left.length()
           else:
              left = 0
           if self.right != None:   
              right = self.right.length()
           else:
              right = 0

           return left + right + 1
        else:
           return 0

    def rotate_left(self):
         _parent = self.parent
         x = self.right
         self.parent = x
         x.parent = _parent
         if x.left is not None:
             x.left.parent = self
         self.right = x.left
         x.left = self
         return x


    def rotate_right(self):
        _parent = self.parent
        x = self.left
        self.parent = x
        x.parent = _parent;
        if x.right is not None:
            x.right.parent = self
        self.left = x.right
        x.right = self
        return x

    def balance_left(self):

       _left = self.left

       if _left is None:
          return self;

       if _left.balance == state.left_high:
                self.balance = state.balanced
                _left.balance = state.balanced
                self = self.rotate_right()
       elif _left.balance == state.right_high: 
                subright = _left.right
                if subright.balance == state.balanced:
                        self.balance = state.balanced
                        _left.balance = state.balanced
                elif subright.balance == state.right_high:
                        self.balance = state.balanced
                        _left.balance = state.left_high
                elif subright.balance == left_high:
                        root.balance = state.right_high
                        _left.balance = state.balanced
                subright.balance = state.balanced
                _left = _left.rotate_left()
                self.left = _left
                self = self.rotate_right()
       elif _left.balance == state.balanced:
               self.balance = state.left_high
               _left.balance = state.right_high
               self = self.rotate_right()
       return self;

    def balance_right(self):

       _right = self.right

       if _right is None:
          return self;

       if _right.balance == state.right_high:
                self.balance = state.balanced
                _right.balance = state.balanced
                self = self.rotate_left()
       elif _right.balance == state.left_high:
                subleft = _right.left;
                if subleft.balance == state.balanced:
                        self.balance = state.balanced
                        _right.balance = state.balanced
                elif subleft.balance == state.left_high:
                        self.balance = state.balanced
                        _right.balance = state.right_high
                elif subleft.balance == state.right_high:
                        self.balance = state.left_high
                        _right.balance = state.balanced
                subleft.balance = state.balanced
                _right = _right.rotate_right()
                self.right = _right
                self = self.rotate_left()
       elif _right.balance == state.balanced:
                self.balance = state.right_high
                _right.balance = state.left_high
                self = self.rotate_left()
       return self


    def balance_tree(self, direct):
        taller = True
        while taller:
            _parent = self.parent;
            if _parent.left == self:
                next_from =  direction.from_left
            else:
                next_from = direction.from_right;

            if direct == direction.from_left:
                if self.balance == state.left_high:
                        if _parent.is_header():
                            _parent.parent = _parent.parent.balance_left()
                        elif _parent.left == self:
                            _parent.left = _parent.left.balance_left()
                        else:
                            _parent.right = _parent.right.balance_left()
                        taller = False

                elif self.balance == state.balanced:
                        self.balance = state.left_high
                        taller = True

                elif self.balance == state.right_high:
                        self.balance = state.balanced
                        taller = False
            else:
              if self.balance == state.left_high:
                        self.balance = state.balanced
                        taller = False

              elif self.balance ==  state.balanced:
                        self.balance = state.right_high
                        taller = True

              elif self.balance ==  state.right_high:
                        if _parent.is_header():
                            _parent.parent = _parent.parent.balance_right()
                        elif _parent.left == self:
                            _parent.left = _parent.left.balance_right()
                        else:
                            _parent.right = _parent.right.balance_right()
                        taller = False

            if taller:
                if _parent.is_header():
                    taller = False
                else:
                    self = _parent
                    direct = next_from

    def balance_tree_remove(self, _from):

        if self.is_header():
            return;

        shorter = True;

        while shorter:
            _parent = self.parent;
            if _parent.left == self:
                next_from = direction.from_left
            else:
                next_from = direction.from_right

            if _from == direction.from_left:
                if self.balance == state.left_high:
                        shorter = True

                elif self.balance == state.balanced:
                        self.balance = state.right_high;
                        shorter = False

                elif self.balance == state.right_high:
                        if self.right is not None:
                            if self.right.balance == state.balanced:
                                shorter = False
                            else:
                                shorter = True
                        else:
                            shorter = False;

                        if _parent.is_header():
                            _parent.parent = _parent.parent.balance_right()
                        elif _parent.left == self:
                            _parent.left = _parent.left.balance_right();
                        else:
                            _parent.right = _parent.right.balance_right()

            else:
                if self.balance == state.right_high:
                        self.balance = state.balanced
                        shorter = True

                elif self.balance == state.balanced:
                        self.balance = state.left_high
                        shorter = False

                elif self.balance == state.left_high:

                        if self.left is not None:
                            if self.left.balance == state.balanced:
                                shorter = False
                            else:
                                shorter = True
                        else:
                           short = False;

                        if _parent.is_header():
                            _parent.parent = _parent.parent.balance_left();
                        elif _parent.left == self:
                            _parent.left = _parent.left.balance_left();
                        else:
                            _parent.right = _parent.right.balance_left();

            if shorter:
               if _parent.is_header():
                    shorter = False
               else: 
                    _from = next_from
                    self = _parent

    def previous(self):
        if self.is_header():
            return self.right

        if self.left is not None:
            y = self.left
            while y.right is not None:
                y = y.right
            return y

        else: 
            y = self.parent;
            if y.is_header():
                return y

            x = self
            while x == y.left:
                x = y
                y = y.parent

            return y

    def next(self):
        if self.is_header():
            return self.left

        if self.right is not None:
            y = self.right
            while y.left is not None:
                y = y.left
            return y;

        else:
            y = self.parent
            if y.is_header():
                return y

            x = self;         
            while x == y.right:
                x = y
                y = y.parent;

            return y

    def swap_nodes(a, b):

        if b == a.left:
            if b.left is not None:
                b.left.parent = a

            if b.right is not None:
                b.right.parent = a

            if a.right is not None:
                a.right.parent = b

            if not a.parent.is_header():
                if a.parent.left == a:
                    a.parent.left = b
                else:
                    a.parent.right = b;
            else:
                a.parent.parent = b

            b.parent = a.parent
            a.parent = b

            a.left = b.left
            b.left = a

            temp = a.right
            a.right = b.right
            b.right = temp
        elif b == a.right:
            if b.right is not None:
                b.right.parent = a

            if b.left is not None:
               b.left.parent = a

            if a.left is not None:
               a.left.parent = b

            if not a.parent.is_header(): 
                if a.parent.left == a:
                    a.parent.left = b
                else:
                    a.parent.right = b
            else:
               a.parent.parent = b

            b.parent = a.parent
            a.parent = b

            a.right = b.right
            b.right = a

            temp = a.left
            a.left = b.left
            b.left = temp
        elif a == b.left:
            if a.left is not None:
                a.left.parent = b

            if a.right is not None:
                a.right.parent = b

            if b.right is not None:
                b.right.parent = a

            if not parent.is_header(): 
                if b.parent.left == b:
                    b.parent.left = a
                else:
                    b.parent.right = a
            else:
                b.parent.parent = a

            a.parent = b.parent
            b.parent = a

            b.left = a.left
            a.left = b

            temp = a.right
            a.right = b.right
            b.right = temp
        elif a == b.right:
            if a.right is not None:
                a.right.parent = b
            if a.left is not None:
               a.left.parent = b

            if b.left is not None:
               b.left.parent = a

            if not b.parent.is_header():
                if b.parent.left == b:
                    b.parent.left = a
                else:
                    b.parent.right = a
            else:
                b.parent.parent = a

            a.parent = b.parent
            b.parent = a

            b.right = a.right
            a.right = b

            temp = a.left
            a.left = b.left
            b.left = temp
        else:
            if a.parent == b.parent:
                temp = a.parent.left
                a.parent.left = a.parent.right
                a.parent.right = temp
            else:
                if not a.parent.is_header():
                    if a.parent.left == a:
                        a.parent.left = b
                    else:
                        a.parent.right = b
                else:
                    a.parent.parent = b

                if not b.parent.is_header():
                    if b.parent.left == b:
                        b.parent.left = a
                    else:
                        b.parent.right = a
                else:
                    b.parent.parent = a

            if b.left is not None:
                b.left.parent = a

            if b.right is not None:
                b.right.parent = a

            if a.left is not None:
                a.left.parent = b

            if a.right is not None:
                a.right.parent = b

            temp1 = a.left
            a.left = b.left
            b.left = temp1

            temp2 = a.right
            a.right = b.right
            b.right = temp2

            temp3 = a.parent
            a.parent = b.parent
            b.parent = temp3

        balance = a.balance
        a.balance = b.balance
        b.balance = balance

class parent_node(node):

    def __init__(self, parent):
        self.parent = parent
        self.left = None
        self.right = None
        self.balance = state.balanced

class set_node(node):

    def __init__(self, parent, key):
        self.parent = parent
        self.left = None
        self.right = None
        self.balance = state.balanced
        self.key = key

class ordered_set:

    def __init__(self):
        self.header = node()

    def __iter__(self):
        self.node = self.header
        return self

    def __next__(self):
        self.node = self.node.next()
        if self.node.is_header():
            raise StopIteration
        return self.node.key

    def __delitem__(self, key):
          self.remove(key)

    def __lt__(self, other):
        first1 = self.header.left
        last1 = self.header
        first2 = other.header.left
        last2 = other.header

        while (first1 != last1) and (first2 != last2):
           l =  first1.key < first2.key
           if not l: 
              first1 = first1.next();
              first2 = first2.next();
           else:
              return True;

        a = self.__len__()
        b = other.__len__()
        return a < b

    def __hash__(self):
        h = 0
        for i in self:
            h = h + i.__hash__()
        return h    

    def __eq__(self, other):
       if self < other:
          return False
       if other < self:
          return False
       return True

    def __ne__(self, other):
       if self < other:
          return True
       if other < self:
          return True
       return False

    def __len__(self):
        return self.header.parent.length()

    def __getitem__(self, key):
          return self.contains(key)

    def __str__(self):
       l = self.header.right
       s = 
       i = self.header.left
       h = self.header
       while i != h:
           s = s + i.key.__str__()
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s

    def __or__(self, other):
       r = ordered_set()

       first1 = self.header.left
       last1 = self.header
       first2 = other.header.left
       last2 = other.header

       while first1 != last1 and first2 != last2:
          les = first1.key < first2.key
          graater = first2.key < first1.key

          if les:
             r.add(first1.key)
             first1 = first1.next()
          elif graater:
             r.add(first2.key)
             first2 = first2.next()
          else:
             r.add(first1.key)
             first1 = first1.next()
             first2 = first2.next()

       while first1 != last1:
          r.add(first1.key)
          first1 = first1.next()

       while first2 != last2:
          r.add(first2.key)
          first2 = first2.next()

       return r

    def __and__(self, other):
       r = ordered_set()

       first1 = self.header.left
       last1 = self.header
       first2 = other.header.left
       last2 = other.header

       while first1 != last1 and first2 != last2:
          les = first1.key < first2.key
          graater = first2.key < first1.key

          if les:
             first1 = first1.next()
          elif graater:
             first2 = first2.next()
          else:
             r.add(first1.key)
             first1 = first1.next()
             first2 = first2.next()

       return r

    def __xor__(self, other):
       r = ordered_set()

       first1 = self.header.left
       last1 = self.header
       first2 = other.header.left
       last2 = other.header

       while first1 != last1 and first2 != last2:
          les = first1.key < first2.key
          graater = first2.key < first1.key

          if les:
             r.add(first1.key)
             first1 = first1.next()
          elif graater:
             r.add(first2.key)
             first2 = first2.next()
          else:
             first1 = first1.next()
             first2 = first2.next()

       while first1 != last1:
          r.add(first1.key)
          first1 = first1.next()

       while first2 != last2:
          r.add(first2.key)
          first2 = first2.next()

       return r


    def __sub__(self, other):
       r = ordered_set()

       first1 = self.header.left
       last1 = self.header
       first2 = other.header.left
       last2 = other.header

       while first1 != last1 and first2 != last2:
          les = first1.key < first2.key
          graater = first2.key < first1.key

          if les:
             r.add(first1.key)
             first1 = first1.next()
          elif graater:
             r.add(first2.key)
             first2 = first2.next()
          else:
             first1 = first1.next()
             first2 = first2.next()

       while first1 != last1:
          r.add(first1.key)
          first1 = first1.next()

       return r

    def __lshift__(self, data):
       self.add(data)
       return self

    def __rshift__(self, data):
       self.remove(data)
       return self

    def is_subset(self, other):
       first1 = self.header.left
       last1 = self.header
       first2 = other.header.left
       last2 = other.header

       is_subet = True

       while first1 != last1 and first2 != last2:
          if first1.key < first2.key:
              is_subset = False
              break
          elif first2.key < first1.key:
             first2 = first2.next()
          else:
             first1 = first1.next()
             first2 = first2.next()

          if is_subet:
             if first1 != last1:
                is_subet = False

       return is_subet

    def is_superset(self,other):
       return other.is_subset(self)

    def add(self, data):
            if self.header.parent is None:
                self.header.parent = set_node(self.header,data)
                self.header.left = self.header.parent
                self.header.right = self.header.parent
            else:

                root = self.header.parent

                while True:
                    c = root.compare(data)
                    if c >= 0:
                        if root.left is not None:
                            root = root.left
                        else:
                            new_node = set_node(root,data)
                            root.left = new_node

                            if self.header.left == root:
                                 self.header.left = new_node
                            root.balance_tree(direction.from_left)
                            return

                    else:
                        if root.right is not None:
                            root = root.right
                        else:
                            new_node = set_node(root, data)
                            root.right = new_node
                            if self.header.right == root:
                                  self.header.right = new_node
                            root.balance_tree(direction.from_right)
                            return

    def remove(self,data):
        root = self.header.parent;

        while True:
            if root is None:
                raise entry_not_found()

            c  = root.compare(data)

            if c < 0:
               root = root.left;

            elif c > 0:
               root = root.right;

            else:

                 if root.left is not None:
                     if root.right is not None: 
                         replace = root.left
                         while replace.right is not None:
                             replace = replace.right
                         root.swap_nodes(replace)

                 _parent = root.parent

                 if _parent.left == root:
                     _from = direction.from_left
                 else:
                     _from = direction.from_right

                 if self.header.left == root:

                     n = root.next();

                     if n.is_header():
                         self.header.left = self.header
                         self.header.right = self.header
                     else:
                        self.header.left = n
                 elif self.header.right == root: 

                     p = root.previous();

                     if p.is_header():
                          self.header.left = self.header
                          self.header.right = self.header
                     else:
                          self.header.right = p

                 if root.left is None:
                     if _parent == self.header:
                         self.header.parent = root.right
                     elif _parent.left == root:
                         _parent.left = root.right
                     else:
                         _parent.right = root.right

                     if root.right is not None:
                          root.right.parent = _parent

                 else:
                     if _parent == self.header:
                          self.header.parent = root.left
                     elif _parent.left == root:
                         _parent.left = root.left
                     else:
                         _parent.right = root.left

                     if root.left is not None:
                         root.left.parent = _parent;


                 _parent.balance_tree_remove(_from)
                 return   

    def contains(self,data):
        root = self.header.parent;

        while True:
            if root == None:
                return False

            c  = root.compare(data);

            if c > 0:
               root = root.left;

            elif c < 0:
               root = root.right;

            else:

                 return True  


    def find(self,data):
        root = self.header.parent;

        while True:
            if root == None:
                raise entry_not_found()

            c  = root.compare(data);

            if c > 0:
               root = root.left;

            elif c < 0:
               root = root.right;

            else:

                 return root.key;  

class key_value(comparer):

    def __init__(self, key, value):
        self.key = key
        self.value = value

    def compare(self,kv):
        if self.key < kv.key:
             return -1
        elif kv.key < self.key:
             return 1
        else:
             return 0

    def __lt__(self, other):
        return self.key < other.key

    def __str__(self):
        return '(' + self.key.__str__() + ',' + self.value.__str__() + ')'

    def __eq__(self, other):
       return self.key == other.key

    def __hash__(self):
        return hash(self.key)


class dictionary:

    def __init__(self):
        self.set = ordered_set()
        return None

    def __lt__(self, other):
       if self.keys() < other.keys():
          return true

       if other.keys() < self.keys():
          return false

       first1 = self.set.header.left
       last1 = self.set.header
       first2 = other.set.header.left
       last2 = other.set.header

       while (first1 != last1) and (first2 != last2):
          l =  first1.key.value < first2.key.value
          if not l: 
             first1 = first1.next();
             first2 = first2.next();
          else:
             return True;

       a = self.__len__()
       b = other.__len__()
       return a < b


    def add(self, key, value):
       try:
           self.set.remove(key_value(key,None))
       except entry_not_found:
            pass  
       self.set.add(key_value(key,value))
       return

    def remove(self, key):
       self.set.remove(key_value(key,None))
       return

    def clear(self):
       self.set.header = node()

    def sort(self):

      sort_bag = bag()
      for e in self:
        sort_bag.add(e.value)
      keys_set = self.keys()
      self.clear()
      i = sort_bag.__iter__()
      i = sort_bag.__next__()
      try:
        for e in keys_set:
          self.add(e,i)
          i = sort_bag.__next__()
      except:
         return        

    def keys(self):
         keys_set = ordered_set()
         for e in self:
             keys_set.add(e.key)
         return keys_set  

    def __len__(self):
        return self.set.header.parent.length()

    def __str__(self):
       l = self.set.header.right;
       s = 
       i = self.set.header.left;
       h = self.set.header;
       while i != h:
           s = s + 
           s = s + i.key.key.__str__()
           s = s + 
           s = s + i.key.value.__str__()
           s = s + 
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s;

    def __iter__(self):

        self.set.node = self.set.header
        return self

    def __next__(self):
        self.set.node = self.set.node.next()
        if self.set.node.is_header():
            raise StopIteration
        return key_value(self.set.node.key.key,self.set.node.key.value)

    def __getitem__(self, key):
          kv = self.set.find(key_value(key,None))
          return kv.value

    def __setitem__(self, key, value):
          self.add(key,value)
          return

    def __delitem__(self, key):
          self.set.remove(key_value(key,None))


class array:

    def __init__(self):
        self.dictionary = dictionary()
        return None

    def __len__(self):
        return self.dictionary.__len__()

    def push(self, value):
       k = self.dictionary.set.header.right
       if k == self.dictionary.set.header:
           self.dictionary.add(0,value)
       else:
           self.dictionary.add(k.key.key+1,value)
       return

    def pop(self):
       if self.dictionary.set.header.parent != None:
          data = self.dictionary.set.header.right.key.value
          self.remove(self.dictionary.set.header.right.key.key)
          return data

    def add(self, key, value):
       try:
          self.dictionary.remove(key)
       except entry_not_found:
          pass
       self.dictionary.add(key,value)          
       return

    def remove(self, key):
       self.dictionary.remove(key)
       return

    def sort(self):
       self.dictionary.sort()

    def clear(self):
      self.dictionary.header = node();


    def __iter__(self):
        self.dictionary.node = self.dictionary.set.header
        return self

    def __next__(self):
        self.dictionary.node = self.dictionary.node.next()
        if self.dictionary.node.is_header():
            raise StopIteration
        return self.dictionary.node.key.value

    def __getitem__(self, key):
          kv = self.dictionary.set.find(key_value(key,None))
          return kv.value

    def __setitem__(self, key, value):
          self.add(key,value)
          return

    def __delitem__(self, key):
          self.dictionary.remove(key)

    def __lshift__(self, data):
         self.push(data)
         return self

    def __lt__(self, other):
       return self.dictionary < other.dictionary

    def __str__(self):
       l = self.dictionary.set.header.right;
       s = 
       i = self.dictionary.set.header.left;
       h = self.dictionary.set.header;
       while i != h:
           s = s + i.key.value.__str__()
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s;


class bag:

    def __init__(self):
        self.header = node()

    def __iter__(self):
        self.node = self.header
        return self

    def __delitem__(self, key):
          self.remove(key)

    def __next__(self):
        self.node = self.node.next()
        if self.node.is_header():
            raise StopIteration
        return self.node.key

    def __str__(self):
       l = self.header.right;
       s = 
       i = self.header.left;
       h = self.header;
       while i != h:
           s = s + i.key.__str__()
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s;

    def __len__(self):
        return self.header.parent.length()

    def __lshift__(self, data):
       self.add(data)
       return self

    def add(self, data):
            if self.header.parent is None:
                self.header.parent = set_node(self.header,data)
                self.header.left = self.header.parent
                self.header.right = self.header.parent
            else:

                root = self.header.parent

                while True:
                    c = root.compare(data)
                    if c >= 0:
                        if root.left is not None:
                            root = root.left
                        else:
                            new_node = set_node(root,data)
                            root.left = new_node

                            if self.header.left == root:
                                 self.header.left = new_node

                            root.balance_tree(direction.from_left)
                            return

                    else:
                        if root.right is not None:
                            root = root.right
                        else:
                            new_node = set_node(root, data)
                            root.right = new_node

                            if self.header.right == root:
                                  self.header.right = new_node

                            root.balance_tree(direction.from_right)
                            return

    def remove_first(self,data):

        root = self.header.parent;

        while True:
            if root is None:
                return False;

            c  = root.compare(data);

            if c > 0:
               root = root.left;

            elif c < 0:
               root = root.right;

            else:

                 if root.left is not None:
                     if root.right is not None: 
                         replace = root.left;
                         while replace.right is not None:
                             replace = replace.right;
                         root.swap_nodes(replace);

                 _parent = root.parent

                 if _parent.left == root:
                     _from = direction.from_left
                 else:
                     _from = direction.from_right

                 if self.header.left == root:

                     n = root.next();

                     if n.is_header():
                         self.header.left = self.header
                         self.header.right = self.header
                     else:
                        self.header.left = n;
                 elif self.header.right == root: 

                     p = root.previous();

                     if p.is_header():
                          self.header.left = self.header
                          self.header.right = self.header
                     else:
                          self.header.right = p

                 if root.left is None:
                     if _parent == self.header:
                         self.header.parent = root.right
                     elif _parent.left == root:
                         _parent.left = root.right
                     else:
                         _parent.right = root.right

                     if root.right is not None:
                          root.right.parent = _parent

                 else:
                     if _parent == self.header:
                          self.header.parent = root.left
                     elif _parent.left == root:
                         _parent.left = root.left
                     else:
                         _parent.right = root.left

                     if root.left is not None:
                         root.left.parent = _parent;


                 _parent.balance_tree_remove(_from)
                 return True;

    def remove(self,data):
       success = self.remove_first(data)
       while success:
          success = self.remove_first(data)

    def remove_node(self, root):

        if root.left != None and root.right != None:
            replace = root.left
            while replace.right != None:
               replace = replace.right
            root.swap_nodes(replace)

        parent = root.parent;

        if parent.left == root:
           next_from = direction.from_left
        else:
           next_from = direction.from_right

        if self.header.left == root:
            n = root.next()

            if n.is_header():
                self.header.left = self.header;
                self.header.right = self.header
            else:
                self.header.left = n
        elif self.header.right == root:
             p = root.previous()

             if p.is_header(): 
                root.header.left = root.header
                root.header.right = header
             else:
                self.header.right = p

        if root.left == None:
            if parent == self.header:
                self.header.parent = root.right
            elif parent.left == root:
                parent.left = root.right
            else:
                parent.right = root.right

            if root.right != None:
               root.right.parent = parent
        else:
            if parent == self.header:
                self.header.parent = root.left
            elif parent.left == root:
                parent.left = root.left
            else:
                parent.right = root.left

            if root.left != None:
               root.left.parent = parent;

        parent.balance_tree_remove(next_from)

    def remove_at(self, data, ophset):

            p = self.search(data);

            if p == None:
                return
            else:
                lower = p
                after = after(data)

            s = 0
            while True:
                if ophset == s:
                    remove_node(lower);
                    return;
                lower = lower.next_node()
                if after == lower:
                   break
                s = s+1

            return

    def search(self, key):
        s = before(key)
        s.next()
        if s.is_header():
           return None
        c = s.compare(s.key)
        if c != 0:
           return None
        return s


    def before(self, data):
        y = self.header;
        x = self.header.parent;

        while x != None:
            if x.compare(data) >= 0:
                x = x.left;
            else:
                y = x;
                x = x.right;
        return y

    def after(self, data):
        y = self.header;
        x = self.header.parent;

        while x != None:
            if x.compare(data) > 0:
                y = x
                x = x.left
            else:
                x = x.right

        return y;


    def find(self,data):
        root = self.header.parent;

        results = array()

        while True:
            if root is None:
                break;

            p = self.before(data)
            p = p.next()
            if not p.is_header():
               i = p
               l = self.after(data)
               while i != l:
                  results.push(i.key)
                  i = i.next()

               return results
            else:
               break;

        return results

class bag_dictionary:

    def __init__(self):
        self.bag = bag()
        return None

    def add(self, key, value):
       self.bag.add(key_value(key,value))
       return

    def remove(self, key):
       self.bag.remove(key_value(key,None))
       return

    def remove_at(self, key, index):
       self.bag.remove_at(key_value(key,None), index)
       return

    def clear(self):
       self.bag.header = node()

    def __len__(self):
        return self.bag.header.parent.length()

    def __str__(self):
       l = self.bag.header.right;
       s = 
       i = self.bag.header.left;
       h = self.bag.header;
       while i != h:
           s = s + 
           s = s + i.key.key.__str__()
           s = s + 
           s = s + i.key.value.__str__()
           s = s + 
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s;

    def __iter__(self):

        self.bag.node = self.bag.header
        return self

    def __next__(self):
        self.bag.node = self.bag.node.next()
        if self.bag.node.is_header():
            raise StopIteration
        return key_value(self.bag.node.key.key,self.bag.node.key.value)

    def __getitem__(self, key):
          kv_array = self.bag.find(key_value(key,None))
          return kv_array

    def __setitem__(self, key, value):
          self.add(key,value)
          return

    def __delitem__(self, key):
          self.bag.remove(key_value(key,None))

class unordered_set:

    def __init__(self):
        self.bag_dictionary = bag_dictionary()

    def __len__(self):
        return self.bag_dictionary.__len__()

    def __hash__(self):
        h = 0
        for i in self:
            h = h + i.__hash__()
        return h    

    def __eq__(self, other):
        for t in self:
           if not other.contains(t):
              return False
        for u in other:
           if self.contains(u):
              return False
        return true;

    def __ne__(self, other):
        return not self == other

    def __or__(self, other):
       r = unordered_set()

       for t in self:
          r.add(t);

       for u in other:
          if not self.contains(u):
             r.add(u);

       return r

    def __and__(self, other):
       r = unordered_set()

       for t in self:
          if other.contains(t):
              r.add(t)

       for u in other:
              if self.contains(u) and not r.contains(u):
                  r.add(u);

       return r

    def __xor__(self, other):
       r = unordered_set()

       for t in self:
          if not other.contains(t):
             r.add(t)

       for u in other:
          if not self.contains(u) and not r.contains(u):
             r.add(u)

       return r


    def __sub__(self, other):
       r = ordered_set()

       for t in self:
          if not other.contains(t):
             r.add(t);

       return r

    def __lshift__(self, data):
       self.add(data)
       return self

    def __rshift__(self, data):
       self.remove(data)
       return self

    def __getitem__(self, key):
          return self.contains(key)

    def is_subset(self, other):

       is_subet = True

       for t in self:
          if not other.contains(t):
             subset = False
             break

       return is_subet

    def is_superset(self,other):
       return other.is_subset(self)


    def add(self, value):
       if not self.contains(value):
           self.bag_dictionary.add(hash(value),value)
       else:
          raise entry_already_exists()

    def contains(self, data):
            if self.bag_dictionary.bag.header.parent == None:
                return False;
            else:
                index = hash(data);

                _search = self.bag_dictionary.bag.header.parent;

                search_index =  _search.key.key;

                if index < search_index:
                   _search = _search.left

                elif index > search_index:
                   _search = _search.right

                if _search == None:
                    return False

                while _search != None:
                    search_index =  _search.key.key;

                    if index < search_index:
                       _search = _search.left

                    elif index > search_index:
                       _search = _search.right

                    else:
                       break

                if _search == None:
                   return False

                return self.contains_node(data, _search)

    def contains_node(self,data,_node):

        previous = _node.previous()
        save = _node

        while not previous.is_header() and previous.key.key == _node.key.key:
            save = previous;
            previous = previous.previous()

        c = _node.key.value
        _node = save
        if c == data:
           return True

        next = _node.next()
        while not next.is_header() and next.key.key == _node.key.key:
            _node = next
            c = _node.key.value
            if c == data:
               return True;
            next = _node.next()

        return False;

    def find(self,data,_node):

        previous = _node.previous()
        save = _node

        while not previous.is_header() and previous.key.key == _node.key.key:
            save = previous;
            previous = previous.previous();

        _node = save;
        c = _node.key.value
        if c == data:
           return _node

        next = _node.next()
        while not next.is_header() and next.key.key == _node.key.key:
            _node = next
            c = _node.data.value
            if c == data:
               return _node
            next = _node.next()

        return None

    def search(self, data):
        if self.bag_dictionary.bag.header.parent == None:
            return None
        else:
            index = hash(data)

            _search = self.bag_dictionary.bag.header.parent

            c = _search.key.key

            if index < c:
               _search = _search.left;

            elif index > c:
               _search = _search.right;

            while _search != None:

                if index != c:
                   break

                c = _search.key.key

                if index < c:
                   _search = _search.left;

                elif index > c:
                   _search = _search.right;

                else:
                   break

            if _search == None:
               return None

            return self.find(data, _search)

    def remove(self,data):
       found = self.search(data);
       if found != None:
          self.bag_dictionary.bag.remove_node(found);
       else:
          raise entry_not_found()

    def clear(self):
       self.bag_dictionary.bag.header = node()

    def __str__(self):
       l = self.bag_dictionary.bag.header.right;
       s = 
       i = self.bag_dictionary.bag.header.left;
       h = self.bag_dictionary.bag.header;
       while i != h:
           s = s + i.key.value.__str__()
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s;

    def __iter__(self):

        self.bag_dictionary.bag.node = self.bag_dictionary.bag.header
        return self

    def __next__(self):
        self.bag_dictionary.bag.node = self.bag_dictionary.bag.node.next()
        if self.bag_dictionary.bag.node.is_header():
            raise StopIteration
        return self.bag_dictionary.bag.node.key.value


class map:

    def __init__(self):
        self.set = unordered_set()
        return None

    def __len__(self):
        return self.set.__len__()

    def add(self, key, value):
       try:
           self.set.remove(key_value(key,None))
       except entry_not_found:
            pass  
       self.set.add(key_value(key,value))
       return

    def remove(self, key):
       self.set.remove(key_value(key,None))
       return

    def clear(self):
       self.set.clear()

    def __str__(self):
       l = self.set.bag_dictionary.bag.header.right;
       s = 
       i = self.set.bag_dictionary.bag.header.left;
       h = self.set.bag_dictionary.bag.header;
       while i != h:
           s = s + 
           s = s + i.key.value.key.__str__()
           s = s + 
           s = s + i.key.value.value.__str__()
           s = s + 
           if i != l:
               s = s + 
           i = i.next()

       s = s + 
       return s;

    def __iter__(self):

        self.set.node = self.set.bag_dictionary.bag.header
        return self

    def __next__(self):
        self.set.node = self.set.node.next()
        if self.set.node.is_header():
            raise StopIteration
        return key_value(self.set.node.key.key,self.set.node.key.value)

    def __getitem__(self, key):
          kv = self.set.find(key_value(key,None))
          return kv.value

    def __setitem__(self, key, value):
          self.add(key,value)
          return

    def __delitem__(self, key):
          self.remove(key)