try:
  from collections import OrderedDict
except ImportError:
  from UserDict import DictMixin
  class OrderedDict(dict, DictMixin):
    def __init__(self, *args, **bfs11440):
      if (len(args) > 1):
        raise TypeError(('expected at most 1 arguments, got %d' % len(args)))

      try:
        self.bfs11437
      except AttributeError:
        self.clear()

      self.update(*args, **bfs11440)

    def clear(self):
      self.bfs11437 = end = []
      end += [None, end, end]
      self.bfs11441 = {}
      dict.clear(self)

    def __setitem__(self, key, value):
      if (key not in self):
        end = self.bfs11437
        bfs11442 = end[1]
        bfs11442[2] = end[1] = self.bfs11441[key] = [key, bfs11442, end]

      dict.__setitem__(self, key, value)

    def __delitem__(self, key):
      dict.__delitem__(self, key)
      (key, bfs11444, next) = self.bfs11441.pop(key)
      bfs11444[2] = next
      next[1] = bfs11444

    def __iter__(self):
      end = self.bfs11437
      bfs11443 = end[2]
      while (bfs11443 is not end):
        yield bfs11443[0]
        bfs11443 = bfs11443[2]


    def __reversed__(self):
      end = self.bfs11437
      bfs11445 = end[1]
      while (bfs11445 is not end):
        yield bfs11445[0]
        bfs11445 = bfs11445[1]


    def popitem(self, bfs11447=True):
      if (not self):
        raise KeyError('dictionary is empty')

      if bfs11447:
        key = next(reversed(self))
      else:
        key = next(iter(self))

      value = self.pop(key)
      return (key, value)

    def __reduce__(self):
      items = [[k, self[k]] for k in self]
      bfs11446 = (self.bfs11441, self.bfs11437)
      del self.bfs11441
      del self.bfs11437
      bfs11450 = vars(self).copy()
      (self.bfs11441, self.bfs11437) = bfs11446
      if bfs11450:
        return (self.__class__, (items,), bfs11450)

      return (self.__class__, (items,))

    def keys(self):
      return list(self)

    setdefault = DictMixin.setdefault
    update = DictMixin.update
    pop = DictMixin.pop
    values = DictMixin.values
    items = DictMixin.items
    iterkeys = DictMixin.iterkeys
    itervalues = DictMixin.itervalues
    iteritems = DictMixin.iteritems
    def __repr__(self):
      if (not self):
        return ('%s()' % (self.__class__.__name__,))

      return ('%s(%r)' % (self.__class__.__name__, list(self.items())))

    def copy(self):
      return self.__class__(self)

    @classmethod
    def fromkeys(bfs10263, bfs11452, value=None):
      d = bfs10263()
      for key in bfs11452:
        d[key] = value

      return d

    def __eq__(self, bfs11451):
      if isinstance(bfs11451, OrderedDict):
        if (len(self) != len(bfs11451)):
          return False

        for (p, bfs11453) in zip(list(self.items()), list(bfs11451.items())):
          if (p != bfs11453):
            return False


        return True

      return dict.__eq__(self, bfs11451)

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



