






"""simple docstring"""



import random

def 			_snake_case    (					lowerCamelCase__     :   int    ,						lowerCamelCase__     :   Union[str, Any]    ,						lowerCamelCase__     :   Optional[int]  )    ->     Any:
							lowerCamelCase_	:							str									=a[left_index]
							lowerCamelCase_	:							Union[str, Any]									=left_index + 1
							for j in range(left_index + 1    ,						lowerCamelCase__  ):
														if a[j] < pivot:
																					lowerCamelCase_							,						lowerCamelCase_	:							List[str]									=a[i], a[j]
																					i += 1
							lowerCamelCase_							,						lowerCamelCase_	:							List[Any]									=a[i - 1], a[left_index]
							return i - 1

def 			_snake_case    (					lowerCamelCase__     :   int    ,						lowerCamelCase__     :   Optional[int]    ,						lowerCamelCase__     :   List[Any]  )    ->     List[str]:
							if left < right:
														lowerCamelCase_	:							Tuple									=random.randint(lowerCamelCase__    ,						right - 1  )
														lowerCamelCase_							,						lowerCamelCase_	:							str									=(
														    a[left],
														    a[pivot],
														)  # switches the pivot with the left most bound
														lowerCamelCase_	:							List[Any]									=partition(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  )
														quick_sort_random(
														    lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  )  # recursive quicksort to the left of the pivot point
														quick_sort_random(
														    lowerCamelCase__    ,						pivot_index + 1    ,						lowerCamelCase__  )  # recursive quicksort to the right of the pivot point

def 			_snake_case    (					)    ->     Optional[Any]:
							lowerCamelCase_	:							List[str]									=input("Enter numbers separated by a comma:\n"  ).strip()
							lowerCamelCase_	:							Dict									=[int(lowerCamelCase__  ) for item in user_input.split(","  )]

							quick_sort_random(lowerCamelCase__    ,						0    ,						len(lowerCamelCase__  )  )

							print(lowerCamelCase__  )


if __name__ == "__main__":
						main()











"""simple docstring"""



def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   list[int]  )    ->     bool:

							# 1. Validate that path exists between current and next vertices
							if graph[path[curr_ind - 1]][next_ver] == 0:
														return False

							# 2. Validate that next vertex is not already in path
							return not any(vertex == next_ver for vertex in path  )

def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   list[int]    ,						lowerCamelCase__     :   int  )    ->     bool:

							# Base Case
							if curr_ind == len(lowerCamelCase__  ):
														# return whether path exists between current and starting vertices
														return graph[path[curr_ind - 1]][path[0]] == 1

							# Recursive Step
							for next_ver in range(0    ,						len(lowerCamelCase__  )  ):
														if valid_connection(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  ):
																					# Insert current vertex  into path as next transition
																					lowerCamelCase_	:							Tuple									=next_ver
																					# Validate created path
																					if util_hamilton_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						curr_ind + 1  ):
																												return True
																					# Backtrack
																					lowerCamelCase_	:							int									=-1
							return False

def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   int = 0  )    ->     list[int]:
							lowerCamelCase_	:							Optional[Any]									=[-1] * (len(lowerCamelCase__  ) + 1)
							# initialize start and end of path with starting index
							lowerCamelCase_	:							Optional[int]									=start_index
							# evaluate and if we find answer return path either return empty array
							return path if util_hamilton_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						1  ) else []



