from collections import deque, ItemsView, KeysView, ValuesView
from itertools import tee
from reprlib import recursive_repr as _recursive_repr
class OrderedDict(dict):
    'Dictionary that remembers insertion order'
    def __init__(self, *args):
        '''Initialize an ordered dictionary.  The signature is the same as
        regular dictionaries, but keyword arguments are not recommended because
        their insertion order is arbitrary.
        '''
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))
        super().__init__()
        if not hasattr(self, '_keys'):
            self._keys = deque()
        self.update(*args)
    def __setitem__(self, key, value):
        'od.__setitem__(i, y) <==> od[i]=y'
        if key not in self:
            self._keys.append(key)
        super().__setitem__(key, value)
    def __delitem__(self, key):
        'od.__delitem__(y) <==> del od[y]'
        self._keys.remove(key)
        super().__delitem__(key)
    def __iter__(self):
        'od.__iter__() <==> iter(od)'
        return iter(self._keys)
    def __reversed__(self):
        'od.__reversed__() <==> reversed(od)'
        return reversed(self.__key)
    def clear(self):
        'od.clear() -> None.  Remove all items from od.'
        self._keys.clear()
        super().clear()
    def popitem(self, last=True):
        '''od.popitem() -> (k, v), return and remove a (key, value) pair.
        Pairs are returned in LIFO order if last is true or FIFO order if false.
        '''
        if not self:
            raise KeyError('dictionary is empty')
        key = self._keys.pop() if last else self._keys.popleft()
        value = super().pop(key)
        return key, value
    def move_to_end(self, key, last=True):
        '''Move an existing element to the end (or beginning if last==False).
        Raises KeyError if the element does not exist.
        When last=True, acts like a fast version of self[key]=self.pop(key).
        '''
        self._keys.remove(key)
        if last:
            self._keys.append(key)
        else:
            self._keys.appendleft(key)
    def __sizeof__(self):
        sizeof = _sys.getsizeof
        return sizeof(self._keys) + sizeof(self)
    def update(self, *args):
        if not args:
            raise TypeError("update() takes at least 1 argument (0 given)")
        args = args[0]
        tmp = set(self)
        if hasattr(args, "keys"):
            for k in args.keys():
                if k not in tmp:
                    tmp.add(k)
                    self._keys.append(k)
        else:
            args, a = tee(args)
            for k, _ in a:
                if k not in tmp:
                    tmp.add(k)
                    self._keys.append(k)
        super().update(args)
    def keys(self):
        return KeysView(self)
    def items(self):
        return ItemsView(self)
    def values(self):
        return ValuesView(self)
    __marker = object()
    def pop(self, key, default=__marker):
        '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
        value.  If key is not found, d is returned if given, otherwise KeyError
        is raised.
        '''
        if key in self:
            self._keys.remove(key)
            return super().pop(key)
        if default is self.__marker:
            raise KeyError(key)
        return default
    def setdefault(self, key, default=None):
        'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
        if key in self:
            return self[key]
        self[key] = default
        return default
    @_recursive_repr()
    def __repr__(self):
        'od.__repr__() <==> repr(od)'
        if not self:
            return '%s()' % (self.__class__.__name__,)
        return '%s(%r)' % (self.__class__.__name__, list(self.items()))
    def __reduce__(self):
        'Return state information for pickling'
        items = [[k, v] for k, v in self.items()]
        inst_dict = vars(self).copy()
        inst_dict.pop('_keys', None)
        return (self.__class__, (items,), inst_dict)
    def copy(self):
        'od.copy() -> a shallow copy of od'
        return self.__class__(self)
    @classmethod
    def fromkeys(cls, iterable, value=None):
        '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
        If not specified, the value defaults to None.
        '''
        self = cls(((k, value) for k in iterable))
        return self
    def __eq__(self, other):
        '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
        while comparison to a regular mapping is order-insensitive.
        '''
        if isinstance(other, OrderedDict):
            return len(self)==len(other) and \
                   all(p==q for p, q in zip(self.items(), other.items()))
        return super().__eq__(self, other)
    def __ne__(self, other):
        return not (self == other)