<s> """<STR_LIT>""" <EOL> from __future__ import absolute_import <EOL> import subprocess <EOL> from math import ceil as oldceil <EOL> from collections import Mapping , MutableMapping <EOL> from operator import itemgetter as _itemgetter , eq as _eq <EOL> import sys <EOL> import heapq as _heapq <EOL> from _weakref import proxy as _proxy <EOL> from itertools import repeat as _repeat , chain as _chain , starmap as _starmap <EOL> from socket import getaddrinfo , SOCK_STREAM , error , socket <EOL> from future . utils import iteritems , itervalues , PY26 , PY3 <EOL> def ceil ( x ) : <EOL> """<STR_LIT>""" <EOL> return int ( oldceil ( x ) ) <EOL> from itertools import islice <EOL> if PY3 : <EOL> try : <EOL> from _thread import get_ident <EOL> except ImportError : <EOL> from _dummy_thread import get_ident <EOL> else : <EOL> try : <EOL> from thread import get_ident <EOL> except ImportError : <EOL> from dummy_thread import get_ident <EOL> def recursive_repr ( fillvalue = '<STR_LIT>' ) : <EOL> '<STR_LIT>' <EOL> def decorating_function ( user_function ) : <EOL> repr_running = set ( ) <EOL> def wrapper ( self ) : <EOL> key = id ( self ) , get_ident ( ) <EOL> if key in repr_running : <EOL> return fillvalue <EOL> repr_running . add ( key ) <EOL> try : <EOL> result = user_function ( self ) <EOL> finally : <EOL> repr_running . discard ( key ) <EOL> return result <EOL> wrapper . __module__ = getattr ( user_function , '<STR_LIT>' ) <EOL> wrapper . __doc__ = getattr ( user_function , '<STR_LIT>' ) <EOL> wrapper . __name__ = getattr ( user_function , '<STR_LIT>' ) <EOL> wrapper . __annotations__ = getattr ( user_function , '<STR_LIT>' , { } ) <EOL> return wrapper <EOL> return decorating_function <EOL> class _Link ( object ) : <EOL> __slots__ = '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT:key>' , '<STR_LIT>' <EOL> class OrderedDict ( dict ) : <EOL> '<STR_LIT>' <EOL> def __init__ ( * args , ** kwds ) : <EOL> '''<STR_LIT>''' <EOL> if not args : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> self = args [ <NUM_LIT:0> ] <EOL> args = args [ <NUM_LIT:1> : ] <EOL> if len ( args ) > <NUM_LIT:1> : <EOL> raise TypeError ( '<STR_LIT>' % len ( args ) ) <EOL> try : <EOL> self . __root <EOL> except AttributeError : <EOL> self . __hardroot = _Link ( ) <EOL> self . __root = root = _proxy ( self . __hardroot ) <EOL> root . prev = root . next = root <EOL> self . __map = { } <EOL> self . __update ( * args , ** kwds ) <EOL> def __setitem__ ( self , key , value , <EOL> dict_setitem = dict . __setitem__ , proxy = _proxy , Link = _Link ) : <EOL> '<STR_LIT>' <EOL> if key not in self : <EOL> self . __map [ key ] = link = Link ( ) <EOL> root = self . __root <EOL> last = root . prev <EOL> link . prev , link . next , link . key = last , root , key <EOL> last . next = link <EOL> root . prev = proxy ( link ) <EOL> dict_setitem ( self , key , value ) <EOL> def __delitem__ ( self , key , dict_delitem = dict . __delitem__ ) : <EOL> '<STR_LIT>' <EOL> dict_delitem ( self , key ) <EOL> link = self . __map . pop ( key ) <EOL> link_prev = link . prev <EOL> link_next = link . next <EOL> link_prev . next = link_next <EOL> link_next . prev = link_prev <EOL> def __iter__ ( self ) : <EOL> '<STR_LIT>' <EOL> root = self . __root <EOL> curr = root . next <EOL> while curr is not root : <EOL> yield curr . key <EOL> curr = curr . next <EOL> def __reversed__ ( self ) : <EOL> '<STR_LIT>' <EOL> root = self . __root <EOL> curr = root . prev <EOL> while curr is not root : <EOL> yield curr . key <EOL> curr = curr . prev <EOL> def clear ( self ) : <EOL> '<STR_LIT>' <EOL> root = self . __root <EOL> root . prev = root . next = root <EOL> self . __map . clear ( ) <EOL> dict . clear ( self ) <EOL> def popitem ( self , last = True ) : <EOL> '''<STR_LIT>''' <EOL> if not self : <EOL> raise KeyError ( '<STR_LIT>' ) <EOL> root = self . __root <EOL> if last : <EOL> link = root . prev <EOL> link_prev = link . prev <EOL> link_prev . next = root <EOL> root . prev = link_prev <EOL> else : <EOL> link = root . next <EOL> link_next = link . next <EOL> root . next = link_next <EOL> link_next . prev = root <EOL> key = link . key <EOL> del self . __map [ key ] <EOL> value = dict . pop ( self , key ) <EOL> return key , value <EOL> def move_to_end ( self , key , last = True ) : <EOL> '''<STR_LIT>''' <EOL> link = self . __map [ key ] <EOL> link_prev = link . prev <EOL> link_next = link . next <EOL> link_prev . next = link_next <EOL> link_next . prev = link_prev <EOL> root = self . __root <EOL> if last : <EOL> last = root . prev <EOL> link . prev = last <EOL> link . next = root <EOL> last . next = root . prev = link <EOL> else : <EOL> first = root . next <EOL> link . prev = root <EOL> link . next = first <EOL> root . next = first . prev = link <EOL> def __sizeof__ ( self ) : <EOL> sizeof = sys . getsizeof <EOL> n = len ( self ) + <NUM_LIT:1> <EOL> size = sizeof ( self . __dict__ ) <EOL> size += sizeof ( self . __map ) * <NUM_LIT:2> <EOL> size += sizeof ( self . __hardroot ) * n <EOL> size += sizeof ( self . __root ) * n <EOL> return size <EOL> update = __update = MutableMapping . update <EOL> keys = MutableMapping . keys <EOL> values = MutableMapping . values <EOL> items = MutableMapping . items <EOL> __ne__ = MutableMapping . __ne__ <EOL> __marker = object ( ) <EOL> def pop ( self , key , default = __marker ) : <EOL> '''<STR_LIT>''' <EOL> if key in self : <EOL> result = self [ key ] <EOL> del self [ key ] <EOL> return result <EOL> if default is self . __marker : <EOL> raise KeyError ( key ) <EOL> return default <EOL> def setdefault ( self , key , default = None ) : <EOL> '<STR_LIT>' <EOL> if key in self : <EOL> return self [ key ] <EOL> self [ key ] = default <EOL> return default <EOL> @ recursive_repr ( ) <EOL> def __repr__ ( self ) : <EOL> '<STR_LIT>' <EOL> if not self : <EOL> return '<STR_LIT>' % ( self . __class__ . __name__ , ) <EOL> return '<STR_LIT>' % ( self . __class__ . __name__ , list ( self . items ( ) ) ) <EOL> def __reduce__ ( self ) : <EOL> '<STR_LIT>' <EOL> inst_dict = vars ( self ) . copy ( ) <EOL> for k in vars ( OrderedDict ( ) ) : <EOL> inst_dict . pop ( k , None ) <EOL> return self . __class__ , ( ) , inst_dict or None , None , iter ( self . items ( ) ) <EOL> def copy ( self ) : <EOL> '<STR_LIT>' <EOL> return self . __class__ ( self ) <EOL> @ classmethod <EOL> def fromkeys ( cls , iterable , value = None ) : <EOL> '''<STR_LIT>''' <EOL> self = cls ( ) <EOL> for key in iterable : <EOL> self [ key ] = value <EOL> return self <EOL> def __eq__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> if isinstance ( other , OrderedDict ) : <EOL> return dict . __eq__ ( self , other ) and all ( map ( _eq , self , other ) ) <EOL> return dict . __eq__ ( self , other ) <EOL> try : <EOL> from operator import itemgetter <EOL> from heapq import nlargest <EOL> except ImportError : <EOL> pass <EOL> def _count_elements ( mapping , iterable ) : <EOL> '<STR_LIT>' <EOL> mapping_get = mapping . get <EOL> for elem in iterable : <EOL> mapping [ elem ] = mapping_get ( elem , <NUM_LIT:0> ) + <NUM_LIT:1> <EOL> class Counter ( dict ) : <EOL> '''<STR_LIT>''' <EOL> def __init__ ( * args , ** kwds ) : <EOL> '''<STR_LIT>''' <EOL> if not args : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> self = args [ <NUM_LIT:0> ] <EOL> args = args [ <NUM_LIT:1> : ] <EOL> if len ( args ) > <NUM_LIT:1> : <EOL> raise TypeError ( '<STR_LIT>' % len ( args ) ) <EOL> super ( Counter , self ) . __init__ ( ) <EOL> self . update ( * args , ** kwds ) <EOL> def __missing__ ( self , key ) : <EOL> '<STR_LIT>' <EOL> return <NUM_LIT:0> <EOL> def most_common ( self , n = None ) : <EOL> '''<STR_LIT>''' <EOL> if n is None : <EOL> return sorted ( self . items ( ) , key = _itemgetter ( <NUM_LIT:1> ) , reverse = True ) <EOL> return _heapq . nlargest ( n , self . items ( ) , key = _itemgetter ( <NUM_LIT:1> ) ) <EOL> def elements ( self ) : <EOL> '''<STR_LIT>''' <EOL> return _chain . from_iterable ( _starmap ( _repeat , self . items ( ) ) ) <EOL> @ classmethod <EOL> def fromkeys ( cls , iterable , v = None ) : <EOL> raise NotImplementedError ( <EOL> '<STR_LIT>' ) <EOL> def update ( * args , ** kwds ) : <EOL> '''<STR_LIT>''' <EOL> if not args : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> self = args [ <NUM_LIT:0> ] <EOL> args = args [ <NUM_LIT:1> : ] <EOL> if len ( args ) > <NUM_LIT:1> : <EOL> raise TypeError ( '<STR_LIT>' % len ( args ) ) <EOL> iterable = args [ <NUM_LIT:0> ] if args else None <EOL> if iterable is not None : <EOL> if isinstance ( iterable , Mapping ) : <EOL> if self : <EOL> self_get = self . get <EOL> for elem , count in iterable . items ( ) : <EOL> self [ elem ] = count + self_get ( elem , <NUM_LIT:0> ) <EOL> else : <EOL> super ( Counter , self ) . update ( iterable ) <EOL> else : <EOL> _count_elements ( self , iterable ) <EOL> if kwds : <EOL> self . update ( kwds ) <EOL> def subtract ( * args , ** kwds ) : <EOL> '''<STR_LIT>''' <EOL> if not args : <EOL> raise TypeError ( "<STR_LIT>" <EOL> "<STR_LIT>" ) <EOL> self = args [ <NUM_LIT:0> ] <EOL> args = args [ <NUM_LIT:1> : ] <EOL> if len ( args ) > <NUM_LIT:1> : <EOL> raise TypeError ( '<STR_LIT>' % len ( args ) ) <EOL> iterable = args [ <NUM_LIT:0> ] if args else None <EOL> if iterable is not None : <EOL> self_get = self . get <EOL> if isinstance ( iterable , Mapping ) : <EOL> for elem , count in iterable . items ( ) : <EOL> self [ elem ] = self_get ( elem , <NUM_LIT:0> ) - count <EOL> else : <EOL> for elem in iterable : <EOL> self [ elem ] = self_get ( elem , <NUM_LIT:0> ) - <NUM_LIT:1> <EOL> if kwds : <EOL> self . subtract ( kwds ) <EOL> def copy ( self ) : <EOL> '<STR_LIT>' <EOL> return self . __class__ ( self ) <EOL> def __reduce__ ( self ) : <EOL> return self . __class__ , ( dict ( self ) , ) <EOL> def __delitem__ ( self , elem ) : <EOL> '<STR_LIT>' <EOL> if elem in self : <EOL> super ( Counter , self ) . __delitem__ ( elem ) <EOL> def __repr__ ( self ) : <EOL> if not self : <EOL> return '<STR_LIT>' % self . __class__ . __name__ <EOL> try : <EOL> items = '<STR_LIT:U+002CU+0020>' . join ( map ( '<STR_LIT>' . __mod__ , self . most_common ( ) ) ) <EOL> return '<STR_LIT>' % ( self . __class__ . __name__ , items ) <EOL> except TypeError : <EOL> return '<STR_LIT>' . format ( self . __class__ . __name__ , dict ( self ) ) <EOL> def __add__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> if not isinstance ( other , Counter ) : <EOL> return NotImplemented <EOL> result = Counter ( ) <EOL> for elem , count in self . items ( ) : <EOL> newcount = count + other [ elem ] <EOL> if newcount > <NUM_LIT:0> : <EOL> result [ elem ] = newcount <EOL> for elem , count in other . items ( ) : <EOL> if elem not in self and count > <NUM_LIT:0> : <EOL> result [ elem ] = count <EOL> return result <EOL> def __sub__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> if not isinstance ( other , Counter ) : <EOL> return NotImplemented <EOL> result = Counter ( ) <EOL> for elem , count in self . items ( ) : <EOL> newcount = count - other [ elem ] <EOL> if newcount > <NUM_LIT:0> : <EOL> result [ elem ] = newcount <EOL> for elem , count in other . items ( ) : <EOL> if elem not in self and count < <NUM_LIT:0> : <EOL> result [ elem ] = <NUM_LIT:0> - count <EOL> return result <EOL> def __or__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> if not isinstance ( other , Counter ) : <EOL> return NotImplemented <EOL> result = Counter ( ) <EOL> for elem , count in self . items ( ) : <EOL> other_count = other [ elem ] <EOL> newcount = other_count if count < other_count else count <EOL> if newcount > <NUM_LIT:0> : <EOL> result [ elem ] = newcount <EOL> for elem , count in other . items ( ) : <EOL> if elem not in self and count > <NUM_LIT:0> : <EOL> result [ elem ] = count <EOL> return result <EOL> def __and__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> if not isinstance ( other , Counter ) : <EOL> return NotImplemented <EOL> result = Counter ( ) <EOL> for elem , count in self . items ( ) : <EOL> other_count = other [ elem ] <EOL> newcount = count if count < other_count else other_count <EOL> if newcount > <NUM_LIT:0> : <EOL> result [ elem ] = newcount <EOL> return result <EOL> def __pos__ ( self ) : <EOL> '<STR_LIT>' <EOL> return self + Counter ( ) <EOL> def __neg__ ( self ) : <EOL> '''<STR_LIT>''' <EOL> return Counter ( ) - self <EOL> def _keep_positive ( self ) : <EOL> '''<STR_LIT>''' <EOL> nonpositive = [ elem for elem , count in self . items ( ) if not count > <NUM_LIT:0> ] <EOL> for elem in nonpositive : <EOL> del self [ elem ] <EOL> return self <EOL> def __iadd__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> for elem , count in other . items ( ) : <EOL> self [ elem ] += count <EOL> return self . _keep_positive ( ) <EOL> def __isub__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> for elem , count in other . items ( ) : <EOL> self [ elem ] -= count <EOL> return self . _keep_positive ( ) <EOL> def __ior__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> for elem , other_count in other . items ( ) : <EOL> count = self [ elem ] <EOL> if other_count > count : <EOL> self [ elem ] = other_count <EOL> return self . _keep_positive ( ) <EOL> def __iand__ ( self , other ) : <EOL> '''<STR_LIT>''' <EOL> for elem , count in self . items ( ) : <EOL> other_count = other [ elem ] <EOL> if other_count < count : <EOL> self [ elem ] = other_count <EOL> return self . _keep_positive ( ) <EOL> def check_output ( * popenargs , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> if '<STR_LIT>' in kwargs : <EOL> raise ValueError ( '<STR_LIT>' ) <EOL> process = subprocess . Popen ( stdout = subprocess . PIPE , * popenargs , ** kwargs ) <EOL> output , unused_err = process . communicate ( ) <EOL> retcode = process . poll ( ) <EOL> if retcode : <EOL> cmd = kwargs . get ( "<STR_LIT:args>" ) <EOL> if cmd is None : <EOL> cmd = popenargs [ <NUM_LIT:0> ] <EOL> raise subprocess . CalledProcessError ( retcode , cmd ) <EOL> return output <EOL> def count ( start = <NUM_LIT:0> , step = <NUM_LIT:1> ) : <EOL> """<STR_LIT>""" <EOL> while True : <EOL> yield start <EOL> start += step <EOL> class ChainMap ( MutableMapping ) : <EOL> '''<STR_LIT>''' <EOL> def __init__ ( self , * maps ) : <EOL> '''<STR_LIT>''' <EOL> self . maps = list ( maps ) or [ { } ] <EOL> def __missing__ ( self , key ) : <EOL> raise KeyError ( key ) <EOL> def __getitem__ ( self , key ) : <EOL> for mapping in self . maps : <EOL> try : <EOL> return mapping [ key ] <EOL> except KeyError : <EOL> pass <EOL> return self . __missing__ ( key ) <EOL> def get ( self , key , default = None ) : <EOL> return self [ key ] if key in self else default <EOL> def __len__ ( self ) : <EOL> return len ( set ( ) . union ( * self . maps ) ) <EOL> def __iter__ ( self ) : <EOL> return iter ( set ( ) . union ( * self . maps ) ) <EOL> def __contains__ ( self , key ) : <EOL> return any ( key in m for m in self . maps ) <EOL> def __bool__ ( self ) : <EOL> return any ( self . maps ) <EOL> __nonzero__ = __bool__ <EOL> @ recursive_repr ( ) <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' . format ( <EOL> self , '<STR_LIT:U+002CU+0020>' . join ( map ( repr , self . maps ) ) ) <EOL> @ classmethod <EOL> def fromkeys ( cls , iterable , * args ) : <EOL> '<STR_LIT>' <EOL> return cls ( dict . fromkeys ( iterable , * args ) ) <EOL> def copy ( self ) : <EOL> '<STR_LIT>' <EOL> return self . __class__ ( self . maps [ <NUM_LIT:0> ] . copy ( ) , * self . maps [ <NUM_LIT:1> : ] ) <EOL> __copy__ = copy <EOL> def new_child ( self , m = None ) : <EOL> '''<STR_LIT>''' <EOL> if m is None : <EOL> m = { } <EOL> return self . __class__ ( m , * self . maps ) <EOL> @ property <EOL> def parents ( self ) : <EOL> '<STR_LIT>' <EOL> return self . __class__ ( * self . maps [ <NUM_LIT:1> : ] ) <EOL> def __setitem__ ( self , key , value ) : <EOL> self . maps [ <NUM_LIT:0> ] [ key ] = value <EOL> def __delitem__ ( self , key ) : <EOL> try : <EOL> del self . maps [ <NUM_LIT:0> ] [ key ] <EOL> except KeyError : <EOL> raise KeyError ( '<STR_LIT>' . format ( key ) ) <EOL> def popitem ( self ) : <EOL> '<STR_LIT>' <EOL> try : <EOL> return self . maps [ <NUM_LIT:0> ] . popitem ( ) <EOL> except KeyError : <EOL> raise KeyError ( '<STR_LIT>' ) <EOL> def pop ( self , key , * args ) : <EOL> '<STR_LIT>' <EOL> try : <EOL> return self . maps [ <NUM_LIT:0> ] . pop ( key , * args ) <EOL> except KeyError : <EOL> raise KeyError ( '<STR_LIT>' . format ( key ) ) <EOL> def clear ( self ) : <EOL> '<STR_LIT>' <EOL> self . maps [ <NUM_LIT:0> ] . clear ( ) <EOL> from socket import _GLOBAL_DEFAULT_TIMEOUT <EOL> def create_connection ( address , timeout = _GLOBAL_DEFAULT_TIMEOUT , <EOL> source_address = None ) : <EOL> """<STR_LIT>""" <EOL> host , port = address <EOL> err = None <EOL> for res in getaddrinfo ( host , port , <NUM_LIT:0> , SOCK_STREAM ) : <EOL> af , socktype , proto , canonname , sa = res <EOL> sock = None <EOL> try : <EOL> sock = socket ( af , socktype , proto ) <EOL> if timeout is not _GLOBAL_DEFAULT_TIMEOUT : <EOL> sock . settimeout ( timeout ) <EOL> if source_address : <EOL> sock . bind ( source_address ) <EOL> sock . connect ( sa ) <EOL> return sock <EOL> except error as _ : <EOL> err = _ <EOL> if sock is not None : <EOL> sock . close ( ) <EOL> if err is not None : <EOL> raise err <EOL> else : <EOL> raise error ( "<STR_LIT>" ) <EOL> _OrderedDict = OrderedDict <EOL> _Counter = Counter <EOL> _check_output = check_output <EOL> _count = count <EOL> _ceil = ceil <EOL> __count_elements = _count_elements <EOL> _recursive_repr = recursive_repr <EOL> _ChainMap = ChainMap <EOL> _create_connection = create_connection <EOL> if sys . version_info >= ( <NUM_LIT:2> , <NUM_LIT:7> ) : <EOL> from collections import OrderedDict , Counter <EOL> from subprocess import check_output <EOL> from itertools import count <EOL> from socket import create_connection <EOL> if sys . version_info >= ( <NUM_LIT:3> , <NUM_LIT:0> ) : <EOL> from math import ceil <EOL> from collections import _count_elements <EOL> if sys . version_info >= ( <NUM_LIT:3> , <NUM_LIT:3> ) : <EOL> from reprlib import recursive_repr <EOL> from collections import ChainMap </s>
