'''simple docstring'''






from __future__ import annotations

from typing import TypedDict




class    a (       __lowerCAmelCase				):



  """simple docstring"""
  __lowerCAmelCase				      =					42
  __lowerCAmelCase				      =					42






def  UpperCamelCase__					(					_lowercase    :				str     )							->	list[str]:
  if not isinstance(_lowercase   ,    _lowercase     ):
    raise TypeError("""The parameter s type must be str."""     )

  return [s[i:] + s[:i] for i in range(len(_lowercase     )     )]






def  UpperCamelCase__					(					_lowercase    :				str     )							->	BWTTransformDict:
  if not isinstance(_lowercase   ,    _lowercase     ):
    raise TypeError("""The parameter s type must be str."""     )
  if not s:
    raise ValueError("""The parameter s must not be empty."""     )

  __UpperCAmelCase:					Optional[Any]		= all_rotations(_lowercase     )
  rotations.sort()  # sort the list of rotations in alphabetically order
  # make a string composed of the last char of each rotation
  __UpperCAmelCase:					BWTTransformDict		= {
      "bwt_string": "".join([word[-1] for word in rotations]     ),
      "idx_original_string": rotations.index(_lowercase     ),
  }
  return response






def  UpperCamelCase__					(					_lowercase    :				str   ,    _lowercase    :				int     )							->	str:
  if not isinstance(_lowercase   ,    _lowercase     ):
    raise TypeError("""The parameter bwt_string type must be str."""     )
  if not bwt_string:
    raise ValueError("""The parameter bwt_string must not be empty."""     )
  try:
    __UpperCAmelCase:					List[Any]		= int(_lowercase     )
  except ValueError:
    raise TypeError(
        """The parameter idx_original_string type must be int or passive"""
        """ of cast to int."""     )
  if idx_original_string < 0:
    raise ValueError("""The parameter idx_original_string must not be lower than 0."""     )
  if idx_original_string >= len(_lowercase     ):
    raise ValueError(
        """The parameter idx_original_string must be lower than""" """ len(bwt_string)."""     )

  __UpperCAmelCase:					Union[str, Any]		= [""""""] * len(_lowercase     )
  for _ in range(len(_lowercase     )     ):
    for i in range(len(_lowercase     )     ):
      __UpperCAmelCase:					str		= bwt_string[i] + ordered_rotations[i]
    ordered_rotations.sort()
  return ordered_rotations[idx_original_string]


if __name__ == "__main__":
    SCREAMING_SNAKE_CASE_	   =			'Provide a string that I will generate its BWT transform: '
    SCREAMING_SNAKE_CASE_	   =			input(entry_msg).strip()
    SCREAMING_SNAKE_CASE_	   =			bwt_transform(s)
    print(
        F"""Burrows Wheeler transform for string '{s}' results """
        F"""in '{result["bwt_string"]}'"""
    )
    SCREAMING_SNAKE_CASE_	   =			reverse_bwt(result['bwt_string'], result['idx_original_string'])
    print(
        F"""Reversing Burrows Wheeler transform for entry '{result["bwt_string"]}' """
        F"""we get original string '{original_string}'"""
    )
'''simple docstring'''






from __future__ import annotations

SCREAMING_SNAKE_CASE_	   =			10






def  UpperCamelCase__					(					_lowercase    :				list[int]     )							->	list[int]:
  __UpperCAmelCase:					Union[str, Any]		= 1
  __UpperCAmelCase:					Optional[Any]		= max(_lowercase     )
  while placement <= max_digit:
    # declare and initialize empty buckets
    __UpperCAmelCase:					list[list]		= [[] for _ in range(_lowercase     )]
    # split list_of_ints between the buckets
    for i in list_of_ints:
      __UpperCAmelCase:					Optional[Any]		= int((i / placement) % RADIX     )
      buckets[tmp].append(_lowercase     )
    # put each buckets' contents into list_of_ints
    __UpperCAmelCase:					Optional[int]		= 0
    for b in range(_lowercase     ):
      for i in buckets[b]:
        __UpperCAmelCase:					str		= i
        a += 1
        # move to next
    placement *= RADIX
  return list_of_ints


if __name__ == "__main__":
    import doctest

    doctest.testmod()