<s> """<STR_LIT>""" <EOL> from abc import ABCMeta , abstractmethod <EOL> import sys <EOL> __all__ = [ "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , <EOL> "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , <EOL> "<STR_LIT>" , "<STR_LIT>" , <EOL> "<STR_LIT>" , "<STR_LIT>" , <EOL> "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , <EOL> "<STR_LIT>" , "<STR_LIT>" , <EOL> ] <EOL> def _hasattr ( C , attr ) : <EOL> try : <EOL> return any ( attr in B . __dict__ for B in C . __mro__ ) <EOL> except AttributeError : <EOL> return hasattr ( C , attr ) <EOL> class Hashable : <EOL> __metaclass__ = ABCMeta <EOL> @ abstractmethod <EOL> def __hash__ ( self ) : <EOL> return <NUM_LIT:0> <EOL> @ classmethod <EOL> def __subclasshook__ ( cls , C ) : <EOL> if cls is Hashable : <EOL> try : <EOL> for B in C . __mro__ : <EOL> if "<STR_LIT>" in B . __dict__ : <EOL> if B . __dict__ [ "<STR_LIT>" ] : <EOL> return True <EOL> break <EOL> except AttributeError : <EOL> if getattr ( C , "<STR_LIT>" , None ) : <EOL> return True <EOL> return NotImplemented <EOL> class Iterable : <EOL> __metaclass__ = ABCMeta <EOL> @ abstractmethod <EOL> def __iter__ ( self ) : <EOL> while False : <EOL> yield None <EOL> @ classmethod <EOL> def __subclasshook__ ( cls , C ) : <EOL> if cls is Iterable : <EOL> if _hasattr ( C , "<STR_LIT>" ) : <EOL> return True <EOL> return NotImplemented <EOL> Iterable . register ( str ) <EOL> class Iterator ( Iterable ) : <EOL> @ abstractmethod <EOL> def next ( self ) : <EOL> '<STR_LIT>' <EOL> raise StopIteration <EOL> def __iter__ ( self ) : <EOL> return self <EOL> @ classmethod <EOL> def __subclasshook__ ( cls , C ) : <EOL> if cls is Iterator : <EOL> if _hasattr ( C , "<STR_LIT>" ) and _hasattr ( C , "<STR_LIT>" ) : <EOL> return True <EOL> return NotImplemented <EOL> class Sized : <EOL> __metaclass__ = ABCMeta <EOL> @ abstractmethod <EOL> def __len__ ( self ) : <EOL> return <NUM_LIT:0> <EOL> @ classmethod <EOL> def __subclasshook__ ( cls , C ) : <EOL> if cls is Sized : <EOL> if _hasattr ( C , "<STR_LIT>" ) : <EOL> return True <EOL> return NotImplemented <EOL> class Container : <EOL> __metaclass__ = ABCMeta <EOL> @ abstractmethod <EOL> def __contains__ ( self , x ) : <EOL> return False <EOL> @ classmethod <EOL> def __subclasshook__ ( cls , C ) : <EOL> if cls is Container : <EOL> if _hasattr ( C , "<STR_LIT>" ) : <EOL> return True <EOL> return NotImplemented <EOL> class Callable : <EOL> __metaclass__ = ABCMeta <EOL> @ abstractmethod <EOL> def __call__ ( self , * args , ** kwds ) : <EOL> return False <EOL> @ classmethod <EOL> def __subclasshook__ ( cls , C ) : <EOL> if cls is Callable : <EOL> if _hasattr ( C , "<STR_LIT>" ) : <EOL> return True <EOL> return NotImplemented <EOL> class Set ( Sized , Iterable , Container ) : <EOL> """<STR_LIT>""" <EOL> def __le__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> return NotImplemented <EOL> if len ( self ) > len ( other ) : <EOL> return False <EOL> for elem in self : <EOL> if elem not in other : <EOL> return False <EOL> return True <EOL> def __lt__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> return NotImplemented <EOL> return len ( self ) < len ( other ) and self . __le__ ( other ) <EOL> def __gt__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> return NotImplemented <EOL> return other < self <EOL> def __ge__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> return NotImplemented <EOL> return other <= self <EOL> def __eq__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> return NotImplemented <EOL> return len ( self ) == len ( other ) and self . __le__ ( other ) <EOL> def __ne__ ( self , other ) : <EOL> return not ( self == other ) <EOL> @ classmethod <EOL> def _from_iterable ( cls , it ) : <EOL> '''<STR_LIT>''' <EOL> return cls ( it ) <EOL> def __and__ ( self , other ) : <EOL> if not isinstance ( other , Iterable ) : <EOL> return NotImplemented <EOL> return self . _from_iterable ( value for value in other if value in self ) <EOL> def isdisjoint ( self , other ) : <EOL> '<STR_LIT>' <EOL> for value in other : <EOL> if value in self : <EOL> return False <EOL> return True <EOL> def __or__ ( self , other ) : <EOL> if not isinstance ( other , Iterable ) : <EOL> return NotImplemented <EOL> chain = ( e for s in ( self , other ) for e in s ) <EOL> return self . _from_iterable ( chain ) <EOL> def __sub__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> if not isinstance ( other , Iterable ) : <EOL> return NotImplemented <EOL> other = self . _from_iterable ( other ) <EOL> return self . _from_iterable ( value for value in self <EOL> if value not in other ) <EOL> def __xor__ ( self , other ) : <EOL> if not isinstance ( other , Set ) : <EOL> if not isinstance ( other , Iterable ) : <EOL> return NotImplemented <EOL> other = self . _from_iterable ( other ) <EOL> return ( self - other ) | ( other - self ) <EOL> __hash__ = None <EOL> def _hash ( self ) : <EOL> """<STR_LIT>""" <EOL> MAX = sys . maxint <EOL> MASK = <NUM_LIT:2> * MAX + <NUM_LIT:1> <EOL> n = len ( self ) <EOL> h = <NUM_LIT> * ( n + <NUM_LIT:1> ) <EOL> h &= MASK <EOL> for x in self : <EOL> hx = hash ( x ) <EOL> h ^= ( hx ^ ( hx << <NUM_LIT:16> ) ^ <NUM_LIT> ) * <NUM_LIT> <EOL> h &= MASK <EOL> h = h * <NUM_LIT> + <NUM_LIT> <EOL> h &= MASK <EOL> if h > MAX : <EOL> h -= MASK + <NUM_LIT:1> <EOL> if h == - <NUM_LIT:1> : <EOL> h = <NUM_LIT> <EOL> return h <EOL> Set . register ( frozenset ) <EOL> class MutableSet ( Set ) : <EOL> """<STR_LIT>""" <EOL> @ abstractmethod <EOL> def add ( self , value ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> @ abstractmethod <EOL> def discard ( self , value ) : <EOL> """<STR_LIT>""" <EOL> raise NotImplementedError <EOL> def remove ( self , value ) : <EOL> """<STR_LIT>""" <EOL> if value not in self : <EOL> raise KeyError ( value ) <EOL> self . discard ( value ) <EOL> def pop ( self ) : <EOL> """<STR_LIT>""" <EOL> it = iter ( self ) <EOL> try : <EOL> value = next ( it ) <EOL> except StopIteration : <EOL> raise KeyError <EOL> self . discard ( value ) <EOL> return value <EOL> def clear ( self ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> while True : <EOL> self . pop ( ) <EOL> except KeyError : <EOL> pass <EOL> def __ior__ ( self , it ) : <EOL> for value in it : <EOL> self . add ( value ) <EOL> return self <EOL> def __iand__ ( self , it ) : <EOL> for value in ( self - it ) : <EOL> self . discard ( value ) <EOL> return self <EOL> def __ixor__ ( self , it ) : <EOL> if it is self : <EOL> self . clear ( ) <EOL> else : <EOL> if not isinstance ( it , Set ) : <EOL> it = self . _from_iterable ( it ) <EOL> for value in it : <EOL> if value in self : <EOL> self . discard ( value ) <EOL> else : <EOL> self . add ( value ) <EOL> return self <EOL> def __isub__ ( self , it ) : <EOL> if it is self : <EOL> self . clear ( ) <EOL> else : <EOL> for value in it : <EOL> self . discard ( value ) <EOL> return self <EOL> MutableSet . register ( set ) <EOL> class Mapping ( Sized , Iterable , Container ) : <EOL> """<STR_LIT>""" <EOL> @ abstractmethod <EOL> def __getitem__ ( self , key ) : <EOL> raise KeyError <EOL> def get ( self , key , default = None ) : <EOL> '<STR_LIT>' <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> return default <EOL> def __contains__ ( self , key ) : <EOL> try : <EOL> self [ key ] <EOL> except KeyError : <EOL> return False <EOL> else : <EOL> return True <EOL> def iterkeys ( self ) : <EOL> '<STR_LIT>' <EOL> return iter ( self ) <EOL> def itervalues ( self ) : <EOL> '<STR_LIT>' <EOL> for key in self : <EOL> yield self [ key ] <EOL> def iteritems ( self ) : <EOL> '<STR_LIT>' <EOL> for key in self : <EOL> yield ( key , self [ key ] ) <EOL> def keys ( self ) : <EOL> "<STR_LIT>" <EOL> return list ( self ) <EOL> def items ( self ) : <EOL> "<STR_LIT>" <EOL> return [ ( key , self [ key ] ) for key in self ] <EOL> def values ( self ) : <EOL> "<STR_LIT>" <EOL> return [ self [ key ] for key in self ] <EOL> __hash__ = None <EOL> def __eq__ ( self , other ) : <EOL> if not isinstance ( other , Mapping ) : <EOL> return NotImplemented <EOL> return dict ( self . items ( ) ) == dict ( other . items ( ) ) <EOL> def __ne__ ( self , other ) : <EOL> return not ( self == other ) <EOL> class MappingView ( Sized ) : <EOL> def __init__ ( self , mapping ) : <EOL> self . _mapping = mapping <EOL> def __len__ ( self ) : <EOL> return len ( self . _mapping ) <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' . format ( self ) <EOL> class KeysView ( MappingView , Set ) : <EOL> @ classmethod <EOL> def _from_iterable ( self , it ) : <EOL> return set ( it ) <EOL> def __contains__ ( self , key ) : <EOL> return key in self . _mapping <EOL> def __iter__ ( self ) : <EOL> for key in self . _mapping : <EOL> yield key <EOL> class ItemsView ( MappingView , Set ) : <EOL> @ classmethod <EOL> def _from_iterable ( self , it ) : <EOL> return set ( it ) <EOL> def __contains__ ( self , item ) : <EOL> key , value = item <EOL> try : <EOL> v = self . _mapping [ key ] <EOL> except KeyError : <EOL> return False <EOL> else : <EOL> return v == value <EOL> def __iter__ ( self ) : <EOL> for key in self . _mapping : <EOL> yield ( key , self . _mapping [ key ] ) <EOL> class ValuesView ( MappingView ) : <EOL> def __contains__ ( self , value ) : <EOL> for key in self . _mapping : <EOL> if value == self . _mapping [ key ] : <EOL> return True <EOL> return False <EOL> def __iter__ ( self ) : <EOL> for key in self . _mapping : <EOL> yield self . _mapping [ key ] <EOL> class MutableMapping ( Mapping ) : <EOL> """<STR_LIT>""" <EOL> @ abstractmethod <EOL> def __setitem__ ( self , key , value ) : <EOL> raise KeyError <EOL> @ abstractmethod <EOL> def __delitem__ ( self , key ) : <EOL> raise KeyError <EOL> __marker = object ( ) <EOL> def pop ( self , key , default = __marker ) : <EOL> '''<STR_LIT>''' <EOL> try : <EOL> value = self [ key ] <EOL> except KeyError : <EOL> if default is self . __marker : <EOL> raise <EOL> return default <EOL> else : <EOL> del self [ key ] <EOL> return value <EOL> def popitem ( self ) : <EOL> '''<STR_LIT>''' <EOL> try : <EOL> key = next ( iter ( self ) ) <EOL> except StopIteration : <EOL> raise KeyError <EOL> value = self [ key ] <EOL> del self [ key ] <EOL> return key , value <EOL> def clear ( self ) : <EOL> '<STR_LIT>' <EOL> try : <EOL> while True : <EOL> self . popitem ( ) <EOL> except KeyError : <EOL> pass <EOL> def update ( * args , ** kwds ) : <EOL> '''<STR_LIT>''' <EOL> if len ( args ) > <NUM_LIT:2> : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" . format ( len ( args ) ) ) <EOL> elif not args : <EOL> raise TypeError ( "<STR_LIT>" ) <EOL> self = args [ <NUM_LIT:0> ] <EOL> other = args [ <NUM_LIT:1> ] if len ( args ) >= <NUM_LIT:2> else ( ) <EOL> if isinstance ( other , Mapping ) : <EOL> for key in other : <EOL> self [ key ] = other [ key ] <EOL> elif hasattr ( other , "<STR_LIT>" ) : <EOL> for key in other . keys ( ) : <EOL> self [ key ] = other [ key ] <EOL> else : <EOL> for key , value in other : <EOL> self [ key ] = value <EOL> for key , value in kwds . items ( ) : <EOL> self [ key ] = value <EOL> def setdefault ( self , key , default = None ) : <EOL> '<STR_LIT>' <EOL> try : <EOL> return self [ key ] <EOL> except KeyError : <EOL> self [ key ] = default <EOL> return default <EOL> MutableMapping . register ( dict ) <EOL> class Sequence ( Sized , Iterable , Container ) : <EOL> """<STR_LIT>""" <EOL> @ abstractmethod <EOL> def __getitem__ ( self , index ) : <EOL> raise IndexError <EOL> def __iter__ ( self ) : <EOL> i = <NUM_LIT:0> <EOL> try : <EOL> while True : <EOL> v = self [ i ] <EOL> yield v <EOL> i += <NUM_LIT:1> <EOL> except IndexError : <EOL> return <EOL> def __contains__ ( self , value ) : <EOL> for v in self : <EOL> if v == value : <EOL> return True <EOL> return False <EOL> def __reversed__ ( self ) : <EOL> for i in reversed ( range ( len ( self ) ) ) : <EOL> yield self [ i ] <EOL> def index ( self , value ) : <EOL> '''<STR_LIT>''' <EOL> for i , v in enumerate ( self ) : <EOL> if v == value : <EOL> return i <EOL> raise ValueError <EOL> def count ( self , value ) : <EOL> '<STR_LIT>' <EOL> return sum ( <NUM_LIT:1> for v in self if v == value ) <EOL> Sequence . register ( tuple ) <EOL> Sequence . register ( basestring ) <EOL> Sequence . register ( buffer ) <EOL> Sequence . register ( xrange ) <EOL> class MutableSequence ( Sequence ) : <EOL> """<STR_LIT>""" <EOL> @ abstractmethod <EOL> def __setitem__ ( self , index , value ) : <EOL> raise IndexError <EOL> @ abstractmethod <EOL> def __delitem__ ( self , index ) : <EOL> raise IndexError <EOL> @ abstractmethod <EOL> def insert ( self , index , value ) : <EOL> '<STR_LIT>' <EOL> raise IndexError <EOL> def append ( self , value ) : <EOL> '<STR_LIT>' <EOL> self . insert ( len ( self ) , value ) <EOL> def reverse ( self ) : <EOL> '<STR_LIT>' <EOL> n = len ( self ) <EOL> for i in range ( n // <NUM_LIT:2> ) : <EOL> self [ i ] , self [ n - i - <NUM_LIT:1> ] = self [ n - i - <NUM_LIT:1> ] , self [ i ] <EOL> def extend ( self , values ) : <EOL> '<STR_LIT>' <EOL> for v in values : <EOL> self . append ( v ) <EOL> def pop ( self , index = - <NUM_LIT:1> ) : <EOL> '''<STR_LIT>''' <EOL> v = self [ index ] <EOL> del self [ index ] <EOL> return v <EOL> def remove ( self , value ) : <EOL> '''<STR_LIT>''' <EOL> del self [ self . index ( value ) ] <EOL> def __iadd__ ( self , values ) : <EOL> self . extend ( values ) <EOL> return self <EOL> MutableSequence . register ( list ) </s>
