

def _a			(	SCREAMING_SNAKE_CASE		:      str		)   ->   int:

 """simple docstring"""






 __lowerCAmelCase:       Union[str, Any]            =				0
 for letter in data:
  __lowerCAmelCase:       Dict            =				(hash_ << 4) + ord(SCREAMING_SNAKE_CASE		)
  __lowerCAmelCase:       List[str]            =				hash_ & 0xf_0_0_0_0_0_0_0
  if x != 0:
   hash_ ^= x >> 24
  hash_ &= ~x
 return hash_


if __name__ == "__main__":
  import doctest

  doctest.testmod()








from __future__ import annotations







def _a			(	SCREAMING_SNAKE_CASE		:      list[int]		)   ->   list[int]:

 """simple docstring"""






 if not list_of_ints:
  return []

 if min(SCREAMING_SNAKE_CASE		) < 0:
  raise ValueError('All numbers must be positive'		)

 __lowerCAmelCase:       Tuple            =				max(len(bin(SCREAMING_SNAKE_CASE		)[2:]		) for x in list_of_ints		)
 return _msd_radix_sort(SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE		)







def _a			(	SCREAMING_SNAKE_CASE		:      list[int]   , SCREAMING_SNAKE_CASE		:      int		)   ->   list[int]:

 """simple docstring"""






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

 __lowerCAmelCase:       List[str]            =				[]
 __lowerCAmelCase:       Any            =				[]
 # 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(SCREAMING_SNAKE_CASE		)
  else:
   # number has a zero at bit bit_position
   zeros.append(SCREAMING_SNAKE_CASE		)

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

 # recombine lists
 __lowerCAmelCase:       List[str]            =				zeros
 res.extend(SCREAMING_SNAKE_CASE		)

 return res







def _a			(	SCREAMING_SNAKE_CASE		:      list[int]		)   ->   List[str]:

 """simple docstring"""






 __lowerCAmelCase:       Optional[int]            =				len(SCREAMING_SNAKE_CASE		)
 if not list_of_ints or length == 1:
  return

 if min(SCREAMING_SNAKE_CASE		) < 0:
  raise ValueError('All numbers must be positive'		)

 __lowerCAmelCase:       Optional[int]            =				max(len(bin(SCREAMING_SNAKE_CASE		)[2:]		) for x in list_of_ints		)
 _msd_radix_sort_inplace(SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE   , 0   , SCREAMING_SNAKE_CASE		)







def _a			(	SCREAMING_SNAKE_CASE		:      list[int]   , SCREAMING_SNAKE_CASE		:      int   , SCREAMING_SNAKE_CASE		:      int   , SCREAMING_SNAKE_CASE		:      int		)   ->   str:

 """simple docstring"""






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

 bit_position -= 1

 __lowerCAmelCase:       Optional[int]            =				begin_index
 __lowerCAmelCase:       Optional[Any]            =				end_index - 1
 while i <= j:
  __lowerCAmelCase:       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:       List[str]            =				True

  if changed:
   continue

  __lowerCAmelCase     ,							__lowerCAmelCase:       Union[str, Any]            =				list_of_ints[j], list_of_ints[i]
  j -= 1
  if j != i:
   i += 1

 _msd_radix_sort_inplace(SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE		)
 _msd_radix_sort_inplace(SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE   , SCREAMING_SNAKE_CASE		)


if __name__ == "__main__":
  import doctest

  doctest.testmod()





