<s> import bisect <EOL> __all__ = [ '<STR_LIT>' ] <EOL> class SortedSet ( object ) : <EOL> """<STR_LIT>""" <EOL> def __and__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . intersection ( other ) <EOL> def __cmp__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> def __contains__ ( self , elem ) : <EOL> """<STR_LIT>""" <EOL> if len ( self ) == <NUM_LIT:0> : <EOL> return False <EOL> index = bisect . bisect_left ( self . elements , elem ) <EOL> if index == len ( self ) or cmp ( self . elements [ index ] , elem ) : <EOL> return False <EOL> else : <EOL> return True <EOL> def __delitem__ ( self , index ) : <EOL> """<STR_LIT>""" <EOL> del self . elements [ index ] <EOL> def __delslice__ ( self , lower , upper ) : <EOL> """<STR_LIT>""" <EOL> del self . elements [ lower : upper ] <EOL> def __eq__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , SortedSet ) : <EOL> raise TypeError ( '<STR_LIT>' ) <EOL> return self . elements == other . elements <EOL> def __ge__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , SortedSet ) : <EOL> return False <EOL> return self . issuperset ( other ) <EOL> def __getitem__ ( self , index ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( index , slice ) : <EOL> indices = index . indices ( len ( self ) ) <EOL> return SortedSet ( [ self [ i ] for i in range ( * indices ) ] ) <EOL> return self . elements [ index ] <EOL> def __getslice__ ( self , lower , upper ) : <EOL> """<STR_LIT>""" <EOL> return SortedSet ( self . elements [ lower : upper ] ) <EOL> def __gt__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , SortedSet ) : <EOL> return False <EOL> return self . issuperset ( other ) and ( self != other ) <EOL> def __iand__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> self . intersection_update ( other ) <EOL> def __init__ ( self , iterable = None ) : <EOL> """<STR_LIT>""" <EOL> self . elements = [ ] <EOL> if iterable is not None : <EOL> if isinstance ( iterable , SortedSet ) : <EOL> self . elements = list ( iterable . elements ) <EOL> else : <EOL> for e in iterable : <EOL> self . add ( e ) <EOL> def __ior__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> self . update ( other ) <EOL> def __isub__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> self . difference_update ( other ) <EOL> def __iter__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return iter ( self . elements ) <EOL> def __ixor__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> self . symmetric_difference_update ( other ) <EOL> def __le__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , SortedSet ) : <EOL> return False <EOL> return self . issubset ( other ) <EOL> def __len__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return len ( self . elements ) <EOL> def __lt__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , SortedSet ) : <EOL> return False <EOL> return self . issubset ( other ) and ( self != other ) <EOL> def __ne__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , SortedSet ) : <EOL> raise TypeError ( '<STR_LIT>' ) <EOL> return self . elements != other . elements <EOL> def __or__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . union ( other ) <EOL> def __rand__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self & other <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return '<STR_LIT>' . format ( self = self ) <EOL> def __reversed__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return reversed ( self . elements ) <EOL> def __ror__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self | other <EOL> def __rsub__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return other . difference ( self ) <EOL> def __rxor__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self ^ other <EOL> def __sub__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . difference ( other ) <EOL> def __xor__ ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . symmetric_difference ( other ) <EOL> def add ( self , elem ) : <EOL> """<STR_LIT>""" <EOL> if len ( self ) == <NUM_LIT:0> : <EOL> self . elements . append ( elem ) <EOL> index = bisect . bisect_left ( self . elements , elem ) <EOL> if index == len ( self ) : <EOL> self . elements . append ( elem ) <EOL> elif cmp ( self . elements [ index ] , elem ) : <EOL> self . elements . insert ( index , elem ) <EOL> else : <EOL> self . elements [ index ] = elem <EOL> def clear ( self ) : <EOL> """<STR_LIT>""" <EOL> self . elements = [ ] <EOL> def copy ( self ) : <EOL> """<STR_LIT>""" <EOL> return SortedSet ( self ) <EOL> def difference ( self , * iterables ) : <EOL> """<STR_LIT>""" <EOL> difference = SortedSet ( self ) <EOL> difference . difference_update ( * iterables ) <EOL> return difference <EOL> def difference_update ( self , * iterables ) : <EOL> """<STR_LIT>""" <EOL> for iterable in iterables : <EOL> for elem in iterable : <EOL> self . discard ( elem ) <EOL> def discard ( self , elem ) : <EOL> """<STR_LIT>""" <EOL> if len ( self ) == <NUM_LIT:0> : <EOL> return <EOL> index = bisect . bisect_left ( self . elements , elem ) <EOL> if index == len ( self ) or cmp ( self . elements [ index ] , elem ) : <EOL> return <EOL> else : <EOL> self . elements . pop ( index ) <EOL> def index ( self , elem ) : <EOL> """<STR_LIT>""" <EOL> if len ( self ) == <NUM_LIT:0> : <EOL> raise ValueError ( '<STR_LIT>' % elem ) <EOL> index = bisect . bisect_left ( self . elements , elem ) <EOL> if index == len ( self ) or cmp ( self . elements [ index ] , elem ) : <EOL> raise ValueError ( '<STR_LIT>' % elem ) <EOL> else : <EOL> return index <EOL> def intersection ( self , * iterables ) : <EOL> """<STR_LIT>""" <EOL> intersection = SortedSet ( self ) <EOL> intersection . intersection_update ( * iterables ) <EOL> return intersection <EOL> def intersection_update ( self , * iterables ) : <EOL> """<STR_LIT>""" <EOL> self . elements = filter ( <EOL> lambda elem : all ( [ elem in iterable for iterable in iterables ] ) , <EOL> self . elements <EOL> ) <EOL> def isdisjoint ( self , iterable ) : <EOL> """<STR_LIT>""" <EOL> return not any ( [ elem in iterable for elem in self ] ) <EOL> def issubset ( self , iterable ) : <EOL> """<STR_LIT>""" <EOL> return all ( [ elem in iterable for elem in self ] ) <EOL> def issuperset ( self , iterable ) : <EOL> """<STR_LIT>""" <EOL> return all ( [ elem in self for elem in iterable ] ) <EOL> def pop ( self , index = None ) : <EOL> """<STR_LIT>""" <EOL> if len ( self ) == <NUM_LIT:0> : <EOL> raise KeyError ( '<STR_LIT>' ) <EOL> if index is None : <EOL> return self . elements . pop ( <NUM_LIT:0> ) <EOL> return self . elements . pop ( index ) <EOL> def remove ( self , elem ) : <EOL> """<STR_LIT>""" <EOL> if elem not in self : <EOL> raise KeyError ( elem ) <EOL> self . discard ( elem ) <EOL> def symmetric_difference ( self , iterable ) : <EOL> """<STR_LIT>""" <EOL> symmetric = SortedSet ( self ) <EOL> symmetric . symmetric_difference_update ( iterable ) <EOL> return symmetric <EOL> def symmetric_difference_update ( self , iterable ) : <EOL> """<STR_LIT>""" <EOL> elements = self . elements <EOL> self . elements = [ ] <EOL> for e in elements : <EOL> if e not in iterable : <EOL> self . add ( e ) <EOL> for e in iterable : <EOL> if e not in elements : <EOL> self . add ( e ) <EOL> def union ( self , * iterables ) : <EOL> """<STR_LIT>""" <EOL> union = SortedSet ( self ) <EOL> union . update ( * iterables ) <EOL> return union <EOL> def update ( self , * iterables ) : <EOL> """<STR_LIT>""" <EOL> for iterable in iterables : <EOL> for elem in iterable : <EOL> self . add ( elem ) </s>
