



"""simple docstring"""




def 		__snake_case		(   SCREAMING_SNAKE_CASE__			:		int       ):





     '''simple docstring'''

     if not isinstance(SCREAMING_SNAKE_CASE__		,						SCREAMING_SNAKE_CASE__       ):
          _UpperCAmelCase    :			List[Any]              =					f'Input value of [number={number}] must be an integer'
          raise TypeError(SCREAMING_SNAKE_CASE__       )
     if number < 0 or number % 2 == 1:
          return False
     _UpperCAmelCase    :			str              =					int(number**0.5       )
     return number == number_sqrt * (number_sqrt + 1)


if __name__ == "__main__":
 import doctest

 doctest.testmod()





"""simple docstring"""




def 		__snake_case		(   SCREAMING_SNAKE_CASE__			:		list		,						SCREAMING_SNAKE_CASE__			:		int		,						SCREAMING_SNAKE_CASE__			:		int       )						->     None:





     '''simple docstring'''

     if right <= left:
          return
     _UpperCAmelCase    :			Any              =					left
     _UpperCAmelCase    :			Tuple              =					right
     _UpperCAmelCase    :			List[Any]              =					sorting[left]
     while i <= b:
          if sorting[i] < pivot:
               _UpperCAmelCase       , _UpperCAmelCase    :			List[Any]              =					sorting[i], sorting[a]
               a += 1
               i += 1
          elif sorting[i] > pivot:
               _UpperCAmelCase       , _UpperCAmelCase    :			Any              =					sorting[i], sorting[b]
               b -= 1
          else:
               i += 1
     quick_sort_apartition(SCREAMING_SNAKE_CASE__		,						SCREAMING_SNAKE_CASE__		,						a - 1       )
     quick_sort_apartition(SCREAMING_SNAKE_CASE__		,						b + 1		,						SCREAMING_SNAKE_CASE__       )

def 		__snake_case		(   SCREAMING_SNAKE_CASE__			:		list		,						SCREAMING_SNAKE_CASE__			:		int		,						SCREAMING_SNAKE_CASE__			:		int       )						->     None:





     '''simple docstring'''

     if left < right:
          _UpperCAmelCase    :			Optional[int]              =					lomuto_partition(SCREAMING_SNAKE_CASE__		,						SCREAMING_SNAKE_CASE__		,						SCREAMING_SNAKE_CASE__       )
          quick_sort_lomuto_partition(SCREAMING_SNAKE_CASE__		,						SCREAMING_SNAKE_CASE__		,						pivot_index - 1       )
          quick_sort_lomuto_partition(SCREAMING_SNAKE_CASE__		,						pivot_index + 1		,						SCREAMING_SNAKE_CASE__       )

def 		__snake_case		(   SCREAMING_SNAKE_CASE__			:		list		,						SCREAMING_SNAKE_CASE__			:		int		,						SCREAMING_SNAKE_CASE__			:		int       )						->     int:





     '''simple docstring'''

     _UpperCAmelCase    :			Dict              =					sorting[right]
     _UpperCAmelCase    :			Any              =					left
     for i in range(SCREAMING_SNAKE_CASE__		,						SCREAMING_SNAKE_CASE__       ):
          if sorting[i] < pivot:
               _UpperCAmelCase       , _UpperCAmelCase    :			Dict              =					sorting[i], sorting[store_index]
               store_index += 1
     _UpperCAmelCase       , _UpperCAmelCase    :			List[str]              =					sorting[store_index], sorting[right]
     return store_index

def 		__snake_case		(   SCREAMING_SNAKE_CASE__			:		list       )						->     list:





     '''simple docstring'''

     if len(SCREAMING_SNAKE_CASE__       ) <= 1:
          return sorting
     return (
         three_way_radix_quicksort([i for i in sorting if i < sorting[0]]       )
         + [i for i in sorting if i == sorting[0]]
         + three_way_radix_quicksort([i for i in sorting if i > sorting[0]]       )
     )


if __name__ == "__main__":
 import doctest

 doctest.testmod(verbose=True)

 _lowerCAmelCase       :      Union[str, Any]							=							input("Enter numbers separated by a comma:\n").strip()
 _lowerCAmelCase       :      List[str]							=							[int(item) for item in user_input.split(",")]
 quick_sort_apartition(unsorted, 0, len(unsorted) - 1)
 print(unsorted)
