


from __future__ import annotations







def     __magic_name__  (      lowerCAmelCase_):
	'''simple docstring'''


	if not list_of_ints:
		return []

	if min(lowerCAmelCase_) < 0:
		raise ValueError("All numbers must be positive")

	lowerCamelCase_			:							Optional[Any]      =       max(len(bin(lowerCAmelCase_)[2:]) for x in list_of_ints)
	return _msd_radix_sort(lowerCAmelCase_      ,					lowerCAmelCase_)







def     __magic_name__  (      lowerCAmelCase_      ,					lowerCAmelCase_):
	'''simple docstring'''


	if bit_position == 0 or len(lowerCAmelCase_) in [0, 1]:
		return list_of_ints

	lowerCamelCase_			:							List[str]      =       []
	lowerCamelCase_			:							int      =       []
	# Split numbers based on bit at bit_position from the right
	for number in list_of_ints:
		if (number >> (bit_position - 1)) & 1:
			# number has a one at bit bit_position
			ones.append(lowerCAmelCase_)
		else:
			# number has a zero at bit bit_position
			zeros.append(lowerCAmelCase_)

    # recursively split both lists further
	lowerCamelCase_			:							Union[str, Any]      =       _msd_radix_sort(lowerCAmelCase_      ,					bit_position - 1)
	lowerCamelCase_			:							str      =       _msd_radix_sort(lowerCAmelCase_      ,					bit_position - 1)

	# recombine lists
	lowerCamelCase_			:							Union[str, Any]      =       zeros
	res.extend(lowerCAmelCase_)

	return res







def     __magic_name__  (      lowerCAmelCase_):
	'''simple docstring'''


	lowerCamelCase_			:							Any      =       len(lowerCAmelCase_)
	if not list_of_ints or length == 1:
		return

	if min(lowerCAmelCase_) < 0:
		raise ValueError("All numbers must be positive")

	lowerCamelCase_			:							Any      =       max(len(bin(lowerCAmelCase_)[2:]) for x in list_of_ints)
	_msd_radix_sort_inplace(lowerCAmelCase_      ,					lowerCAmelCase_      ,					0      ,					lowerCAmelCase_)







def     __magic_name__  (      lowerCAmelCase_      ,					lowerCAmelCase_      ,					lowerCAmelCase_      ,					lowerCAmelCase_):
	'''simple docstring'''


	if bit_position == 0 or end_index - begin_index <= 1:
		return

	bit_position -= 1

	lowerCamelCase_			:							Dict      =       begin_index
	lowerCamelCase_			:							List[str]      =       end_index - 1
	while i <= j:
		lowerCamelCase_			:							Optional[Any]      =       False
		if not (list_of_ints[i] >> bit_position) & 1:
			# found zero at the beginning
			i += 1
			lowerCamelCase_			:							Optional[Any]      =       True
		if (list_of_ints[j] >> bit_position) & 1:
			# found one at the end
			j -= 1
			lowerCamelCase_			:							int      =       True

		if changed:
			continue

		lowerCamelCase_   ,lowerCamelCase_			:							int      =       list_of_ints[j], list_of_ints[i]
		j -= 1
		if j != i:
			i += 1

	_msd_radix_sort_inplace(lowerCAmelCase_      ,					lowerCAmelCase_      ,					lowerCAmelCase_      ,					lowerCAmelCase_)
	_msd_radix_sort_inplace(lowerCAmelCase_      ,					lowerCAmelCase_      ,					lowerCAmelCase_      ,					lowerCAmelCase_)


if __name__ == "__main__":
							import doctest

							doctest.testmod()





from ..utils import DummyObject, requires_backends





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		str  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[str]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Tuple  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Any  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Tuple  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		int  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[int]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Tuple  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[int]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Tuple  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		int  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[str]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Dict  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		str  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Dict  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Any  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		int  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		int  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Dict  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Any  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		str  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[int]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Dict  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		str  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		str  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Dict  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Tuple  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Any  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		int  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Optional[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[str]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Tuple  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Any  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Union[str, Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[Any]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Any  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		int  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		Dict  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		List[str]  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )





class    lowerCAmelCase__				(			metaclass=__lowerCamelCase       ):






						"""simple docstring"""
						__UpperCAmelCase   :		str  					=	['''tokenizers''']




						def __init__(   self				,							*a_				,							**a_     ):
							requires_backends(self				,							["tokenizers"]     )

