<s> from __future__ import print_function <EOL> from sys import hexversion <EOL> from . sortedlist import recursive_repr <EOL> from bisect import bisect_left , bisect_right , insort <EOL> from itertools import chain , repeat , starmap <EOL> from collections import MutableSequence <EOL> from operator import iadd , add <EOL> from functools import wraps <EOL> from math import log <EOL> if hexversion < <NUM_LIT> : <EOL> from itertools import izip as zip <EOL> from itertools import imap as map <EOL> else : <EOL> from functools import reduce <EOL> def identity ( value ) : <EOL> return value <EOL> class SortedListWithKey ( MutableSequence ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , iterable = None , key = identity , load = <NUM_LIT:1000> ) : <EOL> """<STR_LIT>""" <EOL> self . _len , self . _maxes , self . _lists , self . _keys , self . _index = <NUM_LIT:0> , [ ] , [ ] , [ ] , [ ] <EOL> self . _key , self . _load , self . _twice , self . _half = key , load , load * <NUM_LIT:2> , load >> <NUM_LIT:1> <EOL> self . _offset = <NUM_LIT:0> <EOL> if iterable is not None : <EOL> self . update ( iterable ) <EOL> def clear ( self ) : <EOL> """<STR_LIT>""" <EOL> self . _len = <NUM_LIT:0> <EOL> del self . _maxes [ : ] <EOL> del self . _lists [ : ] <EOL> del self . _keys [ : ] <EOL> del self . _index [ : ] <EOL> def add ( self , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _lists , _keys = self . _maxes , self . _lists , self . _keys <EOL> key = self . _key ( val ) <EOL> if _maxes : <EOL> pos = bisect_right ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> pos -= <NUM_LIT:1> <EOL> _maxes [ pos ] = key <EOL> _keys [ pos ] . append ( key ) <EOL> _lists [ pos ] . append ( val ) <EOL> else : <EOL> idx = bisect_right ( _keys [ pos ] , key ) <EOL> _keys [ pos ] . insert ( idx , key ) <EOL> _lists [ pos ] . insert ( idx , val ) <EOL> self . _expand ( pos ) <EOL> else : <EOL> _maxes . append ( key ) <EOL> _keys . append ( [ key ] ) <EOL> _lists . append ( [ val ] ) <EOL> self . _len += <NUM_LIT:1> <EOL> def _expand ( self , pos ) : <EOL> """<STR_LIT>""" <EOL> _lists , _keys , _index = self . _lists , self . _keys , self . _index <EOL> if len ( _keys [ pos ] ) > self . _twice : <EOL> _maxes , _load = self . _maxes , self . _load <EOL> half = _keys [ pos ] [ _load : ] <EOL> half_list = _lists [ pos ] [ _load : ] <EOL> del _keys [ pos ] [ _load : ] <EOL> del _lists [ pos ] [ _load : ] <EOL> _maxes [ pos ] = _keys [ pos ] [ - <NUM_LIT:1> ] <EOL> _maxes . insert ( pos + <NUM_LIT:1> , half [ - <NUM_LIT:1> ] ) <EOL> _keys . insert ( pos + <NUM_LIT:1> , half ) <EOL> _lists . insert ( pos + <NUM_LIT:1> , half_list ) <EOL> del _index [ : ] <EOL> else : <EOL> if len ( _index ) > <NUM_LIT:0> : <EOL> child = self . _offset + pos <EOL> while child > <NUM_LIT:0> : <EOL> _index [ child ] += <NUM_LIT:1> <EOL> child = ( child - <NUM_LIT:1> ) >> <NUM_LIT:1> <EOL> _index [ <NUM_LIT:0> ] += <NUM_LIT:1> <EOL> def update ( self , iterable ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _lists , _keys = self . _maxes , self . _lists , self . _keys <EOL> values = sorted ( iterable , key = self . _key ) <EOL> if _maxes : <EOL> if len ( values ) * <NUM_LIT:4> >= self . _len : <EOL> values . extend ( chain . from_iterable ( _lists ) ) <EOL> values . sort ( key = self . _key ) <EOL> self . clear ( ) <EOL> else : <EOL> _add = self . add <EOL> for val in values : <EOL> _add ( val ) <EOL> return <EOL> _load , _index = self . _load , self . _index <EOL> _lists . extend ( values [ pos : ( pos + _load ) ] <EOL> for pos in range ( <NUM_LIT:0> , len ( values ) , _load ) ) <EOL> _keys . extend ( list ( map ( self . _key , _list ) ) for _list in _lists ) <EOL> _maxes . extend ( sublist [ - <NUM_LIT:1> ] for sublist in _keys ) <EOL> self . _len = len ( values ) <EOL> del _index [ : ] <EOL> def __contains__ ( self , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes = self . _maxes <EOL> if not _maxes : <EOL> return False <EOL> key = self . _key ( val ) <EOL> pos = bisect_left ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> return False <EOL> _keys = self . _keys <EOL> _lists = self . _lists <EOL> idx = bisect_left ( _keys [ pos ] , key ) <EOL> len_keys = len ( _keys ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> while True : <EOL> if _keys [ pos ] [ idx ] != key : <EOL> return False <EOL> if _lists [ pos ] [ idx ] == val : <EOL> return True <EOL> idx += <NUM_LIT:1> <EOL> if idx == len_sublist : <EOL> pos += <NUM_LIT:1> <EOL> if pos == len_keys : <EOL> return False <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> idx = <NUM_LIT:0> <EOL> def discard ( self , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes = self . _maxes <EOL> if not _maxes : <EOL> return <EOL> key = self . _key ( val ) <EOL> pos = bisect_left ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> return <EOL> _keys = self . _keys <EOL> _lists = self . _lists <EOL> idx = bisect_left ( _keys [ pos ] , key ) <EOL> len_keys = len ( _keys ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> while True : <EOL> if _keys [ pos ] [ idx ] != key : <EOL> return <EOL> if _lists [ pos ] [ idx ] == val : <EOL> self . _delete ( pos , idx ) <EOL> return <EOL> idx += <NUM_LIT:1> <EOL> if idx == len_sublist : <EOL> pos += <NUM_LIT:1> <EOL> if pos == len_keys : <EOL> return <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> idx = <NUM_LIT:0> <EOL> def remove ( self , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes = self . _maxes <EOL> if not _maxes : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> key = self . _key ( val ) <EOL> pos = bisect_left ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> _keys = self . _keys <EOL> _lists = self . _lists <EOL> idx = bisect_left ( _keys [ pos ] , key ) <EOL> len_keys = len ( _keys ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> while True : <EOL> if _keys [ pos ] [ idx ] != key : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> if _lists [ pos ] [ idx ] == val : <EOL> self . _delete ( pos , idx ) <EOL> return <EOL> idx += <NUM_LIT:1> <EOL> if idx == len_sublist : <EOL> pos += <NUM_LIT:1> <EOL> if pos == len_keys : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> idx = <NUM_LIT:0> <EOL> def _delete ( self , pos , idx ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _lists , _keys , _index = self . _maxes , self . _lists , self . _keys , self . _index <EOL> keys_pos = _keys [ pos ] <EOL> lists_pos = _lists [ pos ] <EOL> del keys_pos [ idx ] <EOL> del lists_pos [ idx ] <EOL> self . _len -= <NUM_LIT:1> <EOL> len_keys_pos = len ( keys_pos ) <EOL> if len_keys_pos > self . _half : <EOL> _maxes [ pos ] = keys_pos [ - <NUM_LIT:1> ] <EOL> if len ( _index ) > <NUM_LIT:0> : <EOL> child = self . _offset + pos <EOL> while child > <NUM_LIT:0> : <EOL> _index [ child ] -= <NUM_LIT:1> <EOL> child = ( child - <NUM_LIT:1> ) >> <NUM_LIT:1> <EOL> _index [ <NUM_LIT:0> ] -= <NUM_LIT:1> <EOL> elif len ( _keys ) > <NUM_LIT:1> : <EOL> if not pos : <EOL> pos += <NUM_LIT:1> <EOL> prev = pos - <NUM_LIT:1> <EOL> _keys [ prev ] . extend ( _keys [ pos ] ) <EOL> _lists [ prev ] . extend ( _lists [ pos ] ) <EOL> _maxes [ prev ] = _keys [ prev ] [ - <NUM_LIT:1> ] <EOL> del _keys [ pos ] <EOL> del _lists [ pos ] <EOL> del _maxes [ pos ] <EOL> del _index [ : ] <EOL> self . _expand ( prev ) <EOL> elif len_keys_pos : <EOL> _maxes [ pos ] = keys_pos [ - <NUM_LIT:1> ] <EOL> else : <EOL> del _keys [ pos ] <EOL> del _lists [ pos ] <EOL> del _maxes [ pos ] <EOL> del _index [ : ] <EOL> def _loc ( self , pos , idx ) : <EOL> """<STR_LIT>""" <EOL> if not pos : <EOL> return idx <EOL> _index = self . _index <EOL> if not len ( _index ) : <EOL> self . _build_index ( ) <EOL> total = <NUM_LIT:0> <EOL> pos += self . _offset <EOL> while pos : <EOL> if not ( pos & <NUM_LIT:1> ) : <EOL> total += _index [ pos - <NUM_LIT:1> ] <EOL> pos = ( pos - <NUM_LIT:1> ) >> <NUM_LIT:1> <EOL> return total + idx <EOL> def _pos ( self , idx ) : <EOL> """<STR_LIT>""" <EOL> if idx < <NUM_LIT:0> : <EOL> last_len = len ( self . _lists [ - <NUM_LIT:1> ] ) <EOL> if ( - idx ) <= last_len : <EOL> return len ( self . _lists ) - <NUM_LIT:1> , last_len + idx <EOL> idx += self . _len <EOL> if idx < <NUM_LIT:0> : <EOL> raise IndexError ( '<STR_LIT>' ) <EOL> elif idx >= self . _len : <EOL> raise IndexError ( '<STR_LIT>' ) <EOL> if idx < len ( self . _lists [ <NUM_LIT:0> ] ) : <EOL> return <NUM_LIT:0> , idx <EOL> _index = self . _index <EOL> if not _index : <EOL> self . _build_index ( ) <EOL> pos = <NUM_LIT:0> <EOL> child = <NUM_LIT:1> <EOL> len_index = len ( _index ) <EOL> while child < len_index : <EOL> index_child = _index [ child ] <EOL> if idx < index_child : <EOL> pos = child <EOL> else : <EOL> idx -= index_child <EOL> pos = child + <NUM_LIT:1> <EOL> child = ( pos << <NUM_LIT:1> ) + <NUM_LIT:1> <EOL> return ( pos - self . _offset , idx ) <EOL> def _build_index ( self ) : <EOL> """<STR_LIT>""" <EOL> row0 = list ( map ( len , self . _lists ) ) <EOL> if len ( row0 ) == <NUM_LIT:1> : <EOL> self . _index [ : ] = row0 <EOL> self . _offset = <NUM_LIT:0> <EOL> return <EOL> head = iter ( row0 ) <EOL> tail = iter ( head ) <EOL> row1 = list ( starmap ( add , zip ( head , tail ) ) ) <EOL> if len ( row0 ) & <NUM_LIT:1> : <EOL> row1 . append ( row0 [ - <NUM_LIT:1> ] ) <EOL> if len ( row1 ) == <NUM_LIT:1> : <EOL> self . _index [ : ] = row1 + row0 <EOL> self . _offset = <NUM_LIT:1> <EOL> return <EOL> size = <NUM_LIT:2> ** ( int ( log ( len ( row1 ) - <NUM_LIT:1> , <NUM_LIT:2> ) ) + <NUM_LIT:1> ) <EOL> row1 . extend ( repeat ( <NUM_LIT:0> , size - len ( row1 ) ) ) <EOL> tree = [ row0 , row1 ] <EOL> while len ( tree [ - <NUM_LIT:1> ] ) > <NUM_LIT:1> : <EOL> head = iter ( tree [ - <NUM_LIT:1> ] ) <EOL> tail = iter ( head ) <EOL> row = list ( starmap ( add , zip ( head , tail ) ) ) <EOL> tree . append ( row ) <EOL> reduce ( iadd , reversed ( tree ) , self . _index ) <EOL> self . _offset = size * <NUM_LIT:2> - <NUM_LIT:1> <EOL> def _slice ( self , slc ) : <EOL> start , stop , step = slc . start , slc . stop , slc . step <EOL> if step == <NUM_LIT:0> : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> if step is None : <EOL> step = <NUM_LIT:1> <EOL> if step > <NUM_LIT:0> : <EOL> if start is None : <EOL> start = <NUM_LIT:0> <EOL> if stop is None : <EOL> stop = len ( self ) <EOL> elif stop < <NUM_LIT:0> : <EOL> stop += len ( self ) <EOL> else : <EOL> if start is None : <EOL> start = len ( self ) - <NUM_LIT:1> <EOL> if stop is None : <EOL> stop = - <NUM_LIT:1> <EOL> elif stop < <NUM_LIT:0> : <EOL> stop += len ( self ) <EOL> if start < <NUM_LIT:0> : <EOL> start += len ( self ) <EOL> if step > <NUM_LIT:0> : <EOL> if start < <NUM_LIT:0> : <EOL> start = <NUM_LIT:0> <EOL> elif start > len ( self ) : <EOL> start = len ( self ) <EOL> if stop < <NUM_LIT:0> : <EOL> stop = <NUM_LIT:0> <EOL> elif stop > len ( self ) : <EOL> stop = len ( self ) <EOL> else : <EOL> if start < <NUM_LIT:0> : <EOL> start = - <NUM_LIT:1> <EOL> elif start >= len ( self ) : <EOL> start = len ( self ) - <NUM_LIT:1> <EOL> if stop < <NUM_LIT:0> : <EOL> stop = - <NUM_LIT:1> <EOL> elif stop > len ( self ) : <EOL> stop = len ( self ) <EOL> return start , stop , step <EOL> def __delitem__ ( self , idx ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( idx , slice ) : <EOL> start , stop , step = self . _slice ( idx ) <EOL> if ( ( step == <NUM_LIT:1> ) and ( start < stop ) <EOL> and ( ( stop - start ) * <NUM_LIT:8> >= self . _len ) ) : <EOL> values = self [ : start ] <EOL> if stop < self . _len : <EOL> values += self [ stop : ] <EOL> self . clear ( ) <EOL> self . update ( values ) <EOL> return <EOL> indices = range ( start , stop , step ) <EOL> if step > <NUM_LIT:0> : <EOL> indices = reversed ( indices ) <EOL> _pos , _delete = self . _pos , self . _delete <EOL> for index in indices : <EOL> pos , idx = _pos ( index ) <EOL> _delete ( pos , idx ) <EOL> else : <EOL> pos , idx = self . _pos ( idx ) <EOL> self . _delete ( pos , idx ) <EOL> def __getitem__ ( self , idx ) : <EOL> """<STR_LIT>""" <EOL> _lists = self . _lists <EOL> if isinstance ( idx , slice ) : <EOL> start , stop , step = self . _slice ( idx ) <EOL> if step == <NUM_LIT:1> and start < stop : <EOL> if start == <NUM_LIT:0> and stop == self . _len : <EOL> return self . as_list ( ) <EOL> start_pos , start_idx = self . _pos ( start ) <EOL> if stop == self . _len : <EOL> stop_pos = len ( _lists ) - <NUM_LIT:1> <EOL> stop_idx = len ( _lists [ stop_pos ] ) <EOL> else : <EOL> stop_pos , stop_idx = self . _pos ( stop ) <EOL> if start_pos == stop_pos : <EOL> return _lists [ start_pos ] [ start_idx : stop_idx ] <EOL> prefix = _lists [ start_pos ] [ start_idx : ] <EOL> middle = _lists [ ( start_pos + <NUM_LIT:1> ) : stop_pos ] <EOL> result = reduce ( iadd , middle , prefix ) <EOL> result += _lists [ stop_pos ] [ : stop_idx ] <EOL> return result <EOL> if step == - <NUM_LIT:1> and start > stop : <EOL> result = self [ ( stop + <NUM_LIT:1> ) : ( start + <NUM_LIT:1> ) ] <EOL> result . reverse ( ) <EOL> return result <EOL> indices = range ( start , stop , step ) <EOL> return list ( self [ index ] for index in indices ) <EOL> else : <EOL> pos , idx = self . _pos ( idx ) <EOL> return _lists [ pos ] [ idx ] <EOL> def _check_order ( self , idx , key , val ) : <EOL> _keys , _len = self . _keys , self . _len <EOL> pos , loc = self . _pos ( idx ) <EOL> if idx < <NUM_LIT:0> : <EOL> idx += _len <EOL> if idx > <NUM_LIT:0> : <EOL> idx_prev = loc - <NUM_LIT:1> <EOL> pos_prev = pos <EOL> if idx_prev < <NUM_LIT:0> : <EOL> pos_prev -= <NUM_LIT:1> <EOL> idx_prev = len ( _keys [ pos_prev ] ) - <NUM_LIT:1> <EOL> if _keys [ pos_prev ] [ idx_prev ] > key : <EOL> msg = '<STR_LIT>' . format ( repr ( val ) , idx ) <EOL> raise ValueError ( msg ) <EOL> if idx < ( _len - <NUM_LIT:1> ) : <EOL> idx_next = loc + <NUM_LIT:1> <EOL> pos_next = pos <EOL> if idx_next == len ( _keys [ pos_next ] ) : <EOL> pos_next += <NUM_LIT:1> <EOL> idx_next = <NUM_LIT:0> <EOL> if _keys [ pos_next ] [ idx_next ] < key : <EOL> msg = '<STR_LIT>' . format ( repr ( val ) , idx ) <EOL> raise ValueError ( msg ) <EOL> def __setitem__ ( self , index , value ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _lists , _keys , _pos = self . _maxes , self . _lists , self . _keys , self . _pos <EOL> _check_order = self . _check_order <EOL> if isinstance ( index , slice ) : <EOL> start , stop , step = self . _slice ( index ) <EOL> indices = range ( start , stop , step ) <EOL> if step != <NUM_LIT:1> : <EOL> if not hasattr ( value , '<STR_LIT>' ) : <EOL> value = list ( value ) <EOL> indices = list ( indices ) <EOL> if len ( value ) != len ( indices ) : <EOL> raise ValueError ( <EOL> '<STR_LIT>' <EOL> '<STR_LIT>' <EOL> . format ( len ( value ) , len ( indices ) ) ) <EOL> log = [ ] <EOL> _append = log . append <EOL> for idx , val in zip ( indices , value ) : <EOL> pos , loc = _pos ( idx ) <EOL> key = self . _key ( val ) <EOL> _append ( ( idx , _keys [ pos ] [ loc ] , key , _lists [ pos ] [ loc ] , val ) ) <EOL> _keys [ pos ] [ loc ] = key <EOL> _lists [ pos ] [ loc ] = val <EOL> if len ( _keys [ pos ] ) == ( loc + <NUM_LIT:1> ) : <EOL> _maxes [ pos ] = key <EOL> try : <EOL> for idx , oldkey , newkey , oldval , newval in log : <EOL> _check_order ( idx , newkey , newval ) <EOL> except ValueError : <EOL> for idx , oldkey , newkey , oldval , newval in log : <EOL> pos , loc = _pos ( idx ) <EOL> _keys [ pos ] [ loc ] = oldkey <EOL> _lists [ pos ] [ loc ] = oldval <EOL> if len ( _keys [ pos ] ) == ( loc + <NUM_LIT:1> ) : <EOL> _maxes [ pos ] = oldkey <EOL> raise <EOL> else : <EOL> if not hasattr ( value , '<STR_LIT>' ) : <EOL> value = list ( value ) <EOL> keys = list ( map ( self . _key , value ) ) <EOL> ordered = all ( keys [ pos - <NUM_LIT:1> ] <= keys [ pos ] <EOL> for pos in range ( <NUM_LIT:1> , len ( keys ) ) ) <EOL> if not ordered : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> if not start or not len ( value ) : <EOL> pass <EOL> else : <EOL> pos , loc = _pos ( start - <NUM_LIT:1> ) <EOL> if _keys [ pos ] [ loc ] > keys [ <NUM_LIT:0> ] : <EOL> msg = '<STR_LIT>' . format ( repr ( value [ <NUM_LIT:0> ] ) , start ) <EOL> raise ValueError ( msg ) <EOL> if stop == len ( self ) or not len ( value ) : <EOL> pass <EOL> else : <EOL> pos , loc = _pos ( stop ) <EOL> if _keys [ pos ] [ loc ] < keys [ - <NUM_LIT:1> ] : <EOL> msg = '<STR_LIT>' . format ( repr ( value [ - <NUM_LIT:1> ] ) , stop ) <EOL> raise ValueError ( msg ) <EOL> del self [ index ] <EOL> _insert = self . insert <EOL> for idx , val in enumerate ( value ) : <EOL> _insert ( start + idx , val ) <EOL> else : <EOL> pos , loc = _pos ( index ) <EOL> key = self . _key ( value ) <EOL> _check_order ( index , key , value ) <EOL> _keys [ pos ] [ loc ] = key <EOL> _lists [ pos ] [ loc ] = value <EOL> if len ( _lists [ pos ] ) == ( loc + <NUM_LIT:1> ) : <EOL> _maxes [ pos ] = key <EOL> def __iter__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return chain . from_iterable ( self . _lists ) <EOL> def __reversed__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return chain . from_iterable ( map ( reversed , reversed ( self . _lists ) ) ) <EOL> def __len__ ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _len <EOL> def bisect_left ( self , val ) : <EOL> """<STR_LIT>""" <EOL> return self . bisect_key_left ( self . _key ( val ) ) <EOL> def bisect_right ( self , val ) : <EOL> """<STR_LIT>""" <EOL> return self . bisect_key_right ( self . _key ( val ) ) <EOL> bisect = bisect_right <EOL> def bisect_key_left ( self , key ) : <EOL> """<STR_LIT>""" <EOL> _maxes = self . _maxes <EOL> if not _maxes : <EOL> return <NUM_LIT:0> <EOL> pos = bisect_left ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> return self . _len <EOL> idx = bisect_left ( self . _keys [ pos ] , key ) <EOL> return self . _loc ( pos , idx ) <EOL> def bisect_key_right ( self , key ) : <EOL> """<STR_LIT>""" <EOL> _maxes = self . _maxes <EOL> if not _maxes : <EOL> return <NUM_LIT:0> <EOL> pos = bisect_right ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> return self . _len <EOL> idx = bisect_right ( self . _keys [ pos ] , key ) <EOL> return self . _loc ( pos , idx ) <EOL> bisect_key = bisect_key_right <EOL> def count ( self , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes = self . _maxes <EOL> if not _maxes : <EOL> return <NUM_LIT:0> <EOL> key = self . _key ( val ) <EOL> pos = bisect_left ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> return <NUM_LIT:0> <EOL> _keys = self . _keys <EOL> _lists = self . _lists <EOL> idx = bisect_left ( _keys [ pos ] , key ) <EOL> total = <NUM_LIT:0> <EOL> len_keys = len ( _keys ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> while True : <EOL> if _keys [ pos ] [ idx ] != key : <EOL> return total <EOL> if _lists [ pos ] [ idx ] == val : <EOL> total += <NUM_LIT:1> <EOL> idx += <NUM_LIT:1> <EOL> if idx == len_sublist : <EOL> pos += <NUM_LIT:1> <EOL> if pos == len_keys : <EOL> return total <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> idx = <NUM_LIT:0> <EOL> def copy ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . __class__ ( self , key = self . _key , load = self . _load ) <EOL> __copy__ = copy <EOL> def append ( self , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _lists , _keys = self . _maxes , self . _lists , self . _keys <EOL> key = self . _key ( val ) <EOL> if not _maxes : <EOL> _maxes . append ( key ) <EOL> _keys . append ( [ key ] ) <EOL> _lists . append ( [ val ] ) <EOL> self . _len = <NUM_LIT:1> <EOL> return <EOL> pos = len ( _keys ) - <NUM_LIT:1> <EOL> if key < _keys [ pos ] [ - <NUM_LIT:1> ] : <EOL> msg = '<STR_LIT>' . format ( repr ( val ) , self . _len ) <EOL> raise ValueError ( msg ) <EOL> _maxes [ pos ] = key <EOL> _keys [ pos ] . append ( key ) <EOL> _lists [ pos ] . append ( val ) <EOL> self . _len += <NUM_LIT:1> <EOL> self . _expand ( pos ) <EOL> def extend ( self , values ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _keys , _lists , _load = self . _maxes , self . _keys , self . _lists , self . _load <EOL> if not isinstance ( values , list ) : <EOL> values = list ( values ) <EOL> keys = list ( map ( self . _key , values ) ) <EOL> if any ( keys [ pos - <NUM_LIT:1> ] > keys [ pos ] <EOL> for pos in range ( <NUM_LIT:1> , len ( keys ) ) ) : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> offset = <NUM_LIT:0> <EOL> if _maxes : <EOL> if keys [ <NUM_LIT:0> ] < _keys [ - <NUM_LIT:1> ] [ - <NUM_LIT:1> ] : <EOL> msg = '<STR_LIT>' . format ( repr ( values [ <NUM_LIT:0> ] ) , self . _len ) <EOL> raise ValueError ( msg ) <EOL> if len ( _keys [ - <NUM_LIT:1> ] ) < self . _half : <EOL> _lists [ - <NUM_LIT:1> ] . extend ( values [ : _load ] ) <EOL> _keys [ - <NUM_LIT:1> ] . extend ( keys [ : _load ] ) <EOL> _maxes [ - <NUM_LIT:1> ] = _keys [ - <NUM_LIT:1> ] [ - <NUM_LIT:1> ] <EOL> offset = _load <EOL> len_keys = len ( _keys ) <EOL> for idx in range ( offset , len ( keys ) , _load ) : <EOL> _lists . append ( values [ idx : ( idx + _load ) ] ) <EOL> _keys . append ( keys [ idx : ( idx + _load ) ] ) <EOL> _maxes . append ( _keys [ - <NUM_LIT:1> ] [ - <NUM_LIT:1> ] ) <EOL> _index = self . _index <EOL> if len_keys == len ( _keys ) : <EOL> len_index = len ( _index ) <EOL> if len_index > <NUM_LIT:0> : <EOL> len_values = len ( values ) <EOL> child = len_index - <NUM_LIT:1> <EOL> while child : <EOL> _index [ child ] += len_values <EOL> child = ( child - <NUM_LIT:1> ) >> <NUM_LIT:1> <EOL> _index [ <NUM_LIT:0> ] += len_values <EOL> else : <EOL> del _index [ : ] <EOL> self . _len += len ( values ) <EOL> def insert ( self , idx , val ) : <EOL> """<STR_LIT>""" <EOL> _maxes , _lists , _keys , _len = self . _maxes , self . _lists , self . _keys , self . _len <EOL> if idx < <NUM_LIT:0> : <EOL> idx += _len <EOL> if idx < <NUM_LIT:0> : <EOL> idx = <NUM_LIT:0> <EOL> if idx > _len : <EOL> idx = _len <EOL> key = self . _key ( val ) <EOL> if not _maxes : <EOL> _maxes . append ( key ) <EOL> _lists . append ( [ val ] ) <EOL> _keys . append ( [ key ] ) <EOL> self . _len = <NUM_LIT:1> <EOL> return <EOL> if not idx : <EOL> if key > _keys [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] : <EOL> msg = '<STR_LIT>' . format ( repr ( val ) , <NUM_LIT:0> ) <EOL> raise ValueError ( msg ) <EOL> else : <EOL> _keys [ <NUM_LIT:0> ] . insert ( <NUM_LIT:0> , key ) <EOL> _lists [ <NUM_LIT:0> ] . insert ( <NUM_LIT:0> , val ) <EOL> self . _expand ( <NUM_LIT:0> ) <EOL> self . _len += <NUM_LIT:1> <EOL> return <EOL> if idx == _len : <EOL> pos = len ( _keys ) - <NUM_LIT:1> <EOL> if _keys [ pos ] [ - <NUM_LIT:1> ] > key : <EOL> msg = '<STR_LIT>' . format ( repr ( val ) , _len ) <EOL> raise ValueError ( msg ) <EOL> else : <EOL> _keys [ pos ] . append ( key ) <EOL> _lists [ pos ] . append ( val ) <EOL> _maxes [ pos ] = _keys [ pos ] [ - <NUM_LIT:1> ] <EOL> self . _expand ( pos ) <EOL> self . _len += <NUM_LIT:1> <EOL> return <EOL> pos , idx = self . _pos ( idx ) <EOL> idx_before = idx - <NUM_LIT:1> <EOL> if idx_before < <NUM_LIT:0> : <EOL> pos_before = pos - <NUM_LIT:1> <EOL> idx_before = len ( _keys [ pos_before ] ) - <NUM_LIT:1> <EOL> else : <EOL> pos_before = pos <EOL> before = _keys [ pos_before ] [ idx_before ] <EOL> if before <= key <= _keys [ pos ] [ idx ] : <EOL> _lists [ pos ] . insert ( idx , val ) <EOL> _keys [ pos ] . insert ( idx , key ) <EOL> self . _expand ( pos ) <EOL> self . _len += <NUM_LIT:1> <EOL> else : <EOL> msg = '<STR_LIT>' . format ( repr ( val ) , idx ) <EOL> raise ValueError ( msg ) <EOL> def pop ( self , idx = - <NUM_LIT:1> ) : <EOL> """<STR_LIT>""" <EOL> if ( idx < <NUM_LIT:0> and - idx > self . _len ) or ( idx >= self . _len ) : <EOL> raise IndexError ( '<STR_LIT>' ) <EOL> pos , idx = self . _pos ( idx ) <EOL> val = self . _lists [ pos ] [ idx ] <EOL> self . _delete ( pos , idx ) <EOL> return val <EOL> def index ( self , val , start = None , stop = None ) : <EOL> """<STR_LIT>""" <EOL> _len , _maxes = self . _len , self . _maxes <EOL> if not _maxes : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> if start is None : <EOL> start = <NUM_LIT:0> <EOL> if start < <NUM_LIT:0> : <EOL> start += _len <EOL> if start < <NUM_LIT:0> : <EOL> start = <NUM_LIT:0> <EOL> if stop is None : <EOL> stop = _len <EOL> if stop < <NUM_LIT:0> : <EOL> stop += _len <EOL> if stop > _len : <EOL> stop = _len <EOL> if stop <= start : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> stop -= <NUM_LIT:1> <EOL> key = self . _key ( val ) <EOL> pos = bisect_left ( _maxes , key ) <EOL> if pos == len ( _maxes ) : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> _keys = self . _keys <EOL> _lists = self . _lists <EOL> idx = bisect_left ( _keys [ pos ] , key ) <EOL> len_keys = len ( _keys ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> while True : <EOL> if _keys [ pos ] [ idx ] != key : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> if _lists [ pos ] [ idx ] == val : <EOL> loc = self . _loc ( pos , idx ) <EOL> if start <= loc <= stop : <EOL> return loc <EOL> elif loc > stop : <EOL> break <EOL> idx += <NUM_LIT:1> <EOL> if idx == len_sublist : <EOL> pos += <NUM_LIT:1> <EOL> if pos == len_keys : <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> len_sublist = len ( _keys [ pos ] ) <EOL> idx = <NUM_LIT:0> <EOL> raise ValueError ( '<STR_LIT>' . format ( repr ( val ) ) ) <EOL> def as_list ( self ) : <EOL> """<STR_LIT>""" <EOL> return reduce ( iadd , self . _lists , [ ] ) <EOL> def __add__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> values = self . as_list ( ) <EOL> values . extend ( that ) <EOL> return self . __class__ ( values , key = self . _key , load = self . _load ) <EOL> def __iadd__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> self . update ( that ) <EOL> return self <EOL> def __mul__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> values = self . as_list ( ) * that <EOL> return self . __class__ ( values , key = self . _key , load = self . _load ) <EOL> def __imul__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> values = self . as_list ( ) * that <EOL> self . clear ( ) <EOL> self . update ( values ) <EOL> return self <EOL> def __eq__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> return ( ( self . _len == len ( that ) ) <EOL> and all ( lhs == rhs for lhs , rhs in zip ( self , that ) ) ) <EOL> def __ne__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> return ( ( self . _len != len ( that ) ) <EOL> or any ( lhs != rhs for lhs , rhs in zip ( self , that ) ) ) <EOL> def __lt__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> return ( ( self . _len <= len ( that ) ) <EOL> and all ( lhs < rhs for lhs , rhs in zip ( self , that ) ) ) <EOL> def __le__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> return ( ( self . _len <= len ( that ) ) <EOL> and all ( lhs <= rhs for lhs , rhs in zip ( self , that ) ) ) <EOL> def __gt__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> return ( ( self . _len >= len ( that ) ) <EOL> and all ( lhs > rhs for lhs , rhs in zip ( self , that ) ) ) <EOL> def __ge__ ( self , that ) : <EOL> """<STR_LIT>""" <EOL> return ( ( self . _len >= len ( that ) ) <EOL> and all ( lhs >= rhs for lhs , rhs in zip ( self , that ) ) ) <EOL> @ recursive_repr <EOL> def __repr__ ( self ) : <EOL> """<STR_LIT>""" <EOL> temp = '<STR_LIT>' <EOL> return temp . format ( <EOL> self . __class__ . __name__ , <EOL> repr ( list ( self ) ) , <EOL> repr ( self . _key ) , <EOL> repr ( self . _load ) <EOL> ) <EOL> def _check ( self ) : <EOL> try : <EOL> assert self . _load >= <NUM_LIT:4> <EOL> assert self . _half == ( self . _load >> <NUM_LIT:1> ) <EOL> assert self . _twice == ( self . _load * <NUM_LIT:2> ) <EOL> if self . _maxes == [ ] : <EOL> assert self . _keys == [ ] <EOL> assert self . _lists == [ ] <EOL> return <EOL> assert len ( self . _maxes ) > <NUM_LIT:0> and len ( self . _keys ) > <NUM_LIT:0> and len ( self . _lists ) > <NUM_LIT:0> <EOL> assert all ( sublist [ pos - <NUM_LIT:1> ] <= sublist [ pos ] <EOL> for sublist in self . _keys <EOL> for pos in range ( <NUM_LIT:1> , len ( sublist ) ) ) <EOL> for pos in range ( <NUM_LIT:1> , len ( self . _keys ) ) : <EOL> assert self . _keys [ pos - <NUM_LIT:1> ] [ - <NUM_LIT:1> ] <= self . _keys [ pos ] [ <NUM_LIT:0> ] <EOL> assert len ( self . _maxes ) == len ( self . _lists ) == len ( self . _keys ) <EOL> assert all ( len ( val_list ) == len ( key_list ) <EOL> for val_list , key_list in zip ( self . _lists , self . _keys ) ) <EOL> assert all ( self . _key ( val ) == key for val , key in <EOL> zip ( ( _val for _val_list in self . _lists for _val in _val_list ) , <EOL> ( _key for _key_list in self . _keys for _key in _key_list ) ) ) <EOL> assert all ( self . _maxes [ pos ] == self . _keys [ pos ] [ - <NUM_LIT:1> ] <EOL> for pos in range ( len ( self . _maxes ) ) ) <EOL> assert all ( len ( sublist ) <= self . _twice for sublist in self . _lists ) <EOL> assert all ( len ( self . _lists [ pos ] ) >= self . _half <EOL> for pos in range ( <NUM_LIT:0> , len ( self . _lists ) - <NUM_LIT:1> ) ) <EOL> assert self . _len == sum ( len ( sublist ) for sublist in self . _lists ) <EOL> if len ( self . _index ) : <EOL> assert len ( self . _index ) == self . _offset + len ( self . _lists ) <EOL> assert self . _len == self . _index [ <NUM_LIT:0> ] <EOL> def test_offset_pos ( pos ) : <EOL> from_index = self . _index [ self . _offset + pos ] <EOL> return from_index == len ( self . _lists [ pos ] ) <EOL> assert all ( test_offset_pos ( pos ) <EOL> for pos in range ( len ( self . _lists ) ) ) <EOL> for pos in range ( self . _offset ) : <EOL> child = ( pos << <NUM_LIT:1> ) + <NUM_LIT:1> <EOL> if self . _index [ pos ] == <NUM_LIT:0> : <EOL> assert child >= len ( self . _index ) <EOL> elif child + <NUM_LIT:1> == len ( self . _index ) : <EOL> assert self . _index [ pos ] == self . _index [ child ] <EOL> else : <EOL> child_sum = self . _index [ child ] + self . _index [ child + <NUM_LIT:1> ] <EOL> assert self . _index [ pos ] == child_sum <EOL> except : <EOL> import sys <EOL> import traceback <EOL> traceback . print_exc ( file = sys . stdout ) <EOL> print ( '<STR_LIT>' , self . _len ) <EOL> print ( '<STR_LIT>' , self . _load , self . _half , self . _twice ) <EOL> print ( '<STR_LIT>' , self . _offset ) <EOL> print ( '<STR_LIT>' , len ( self . _index ) ) <EOL> print ( '<STR_LIT:index>' , self . _index ) <EOL> print ( '<STR_LIT>' , len ( self . _maxes ) ) <EOL> print ( '<STR_LIT>' , self . _maxes ) <EOL> print ( '<STR_LIT>' , len ( self . _keys ) ) <EOL> print ( '<STR_LIT>' , self . _keys ) <EOL> print ( '<STR_LIT>' , len ( self . _lists ) ) <EOL> print ( '<STR_LIT>' , self . _lists ) <EOL> raise </s>
