



import math






def      _A				(UpperCamelCase		:      Optional[Any]      ,			UpperCamelCase		:      Tuple = 0      ,			UpperCamelCase		:      Dict = 0 )  ->int:



			'''simple docstring'''







			lowerCamelCase__ :      Union[str, Any]								=		end or len(lowercase__ )
			for i in range(lowercase__      ,			lowercase__ ):
						lowerCamelCase__ :      Any								=		i
						lowerCamelCase__ :      Optional[Any]								=		array[i]
						while temp_index != start and temp_index_value < array[temp_index - 1]:
									lowerCamelCase__ :      Union[str, Any]								=		array[temp_index - 1]
									temp_index -= 1
						lowerCamelCase__ :      Any								=		temp_index_value
			return array






def      _A				(UpperCamelCase		:      str      ,			UpperCamelCase		:      List[Any]      ,			UpperCamelCase		:      Dict )  ->Optional[int]:  # Max Heap



			'''simple docstring'''







			lowerCamelCase__ :      List[Any]								=		index
			lowerCamelCase__ :      str								=		2 * index + 1  # Left Node
			lowerCamelCase__ :      Union[str, Any]								=		2 * index + 2  # Right Node

			if left_index < heap_size and array[largest] < array[left_index]:
						lowerCamelCase__ :      Optional[Any]								=		left_index

			if right_index < heap_size and array[largest] < array[right_index]:
						lowerCamelCase__ :      Any								=		right_index

			if largest != index:
						lowerCamelCase__							,lowerCamelCase__ :      List[str]								=		array[largest], array[index]
						heapify(lowercase__      ,			lowercase__      ,			lowercase__ )






def      _A				(UpperCamelCase		:      str )  ->int:



			'''simple docstring'''







			lowerCamelCase__ :      Optional[Any]								=		len(lowercase__ )

			for i in range(n // 2      ,			-1      ,			-1 ):
						heapify(lowercase__      ,			lowercase__      ,			lowercase__ )

			for i in range(n - 1      ,			0      ,			-1 ):
						lowerCamelCase__							,lowerCamelCase__ :      Any								=		array[0], array[i]
						heapify(lowercase__      ,			0      ,			lowercase__ )

			return array






def      _A				(UpperCamelCase		:      List[str]      ,			UpperCamelCase		:      Tuple      ,			UpperCamelCase		:      List[str]      ,			UpperCamelCase		:      Optional[Any] )  ->str:



			'''simple docstring'''







			if (array[first_index] > array[middle_index]) != (
			    array[first_index] > array[last_index]
			):
						return array[first_index]
			elif (array[middle_index] > array[first_index]) != (
			    array[middle_index] > array[last_index]
			):
						return array[middle_index]
			else:
						return array[last_index]






def      _A				(UpperCamelCase		:      Union[str, Any]      ,			UpperCamelCase		:      List[Any]      ,			UpperCamelCase		:      str      ,			UpperCamelCase		:      Optional[int] )  ->Optional[int]:



			'''simple docstring'''







			lowerCamelCase__ :      Dict								=		low
			lowerCamelCase__ :      str								=		high
			while True:
						while array[i] < pivot:
									i += 1
						j -= 1
						while pivot < array[j]:
									j -= 1
						if i >= j:
									return i
						lowerCamelCase__							,lowerCamelCase__ :      Optional[Any]								=		array[j], array[i]
						i += 1






def      _A				(UpperCamelCase		:      Dict )  ->int:



			'''simple docstring'''







			if len(lowercase__ ) == 0:
						return array
			lowerCamelCase__ :      str								=		2 * math.ceil(math.loga(len(lowercase__ ) ) )
			lowerCamelCase__ :      str								=		16
			return intro_sort(lowercase__      ,			0      ,			len(lowercase__ )      ,			lowercase__      ,			lowercase__ )






def      _A				(UpperCamelCase		:      Union[str, Any]      ,			UpperCamelCase		:      Any      ,			UpperCamelCase		:      Any      ,			UpperCamelCase		:      Optional[Any]      ,			UpperCamelCase		:      Optional[int] )  ->Any:



			'''simple docstring'''







			while end - start > size_threshold:
						if max_depth == 0:
									return heap_sort(lowercase__ )
						max_depth -= 1
						lowerCamelCase__ :      Optional[int]								=		median_of_a(lowercase__      ,			lowercase__      ,			start + ((end - start) // 2) + 1      ,			end - 1 )
						lowerCamelCase__ :      Any								=		partition(lowercase__      ,			lowercase__      ,			lowercase__      ,			lowercase__ )
						intro_sort(lowercase__      ,			lowercase__      ,			lowercase__      ,			lowercase__      ,			lowercase__ )
						lowerCamelCase__ :      int								=		p
			return insertion_sort(lowercase__      ,			lowercase__      ,			lowercase__ )


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				lowercase__     							=						input('''Enter numbers separated by a comma : ''').strip()
				lowercase__     							=						[float(item) for item in user_input.split(''',''')]
				print(sort(unsorted))








from __future__ import annotations






def      _A				(UpperCamelCase		:      str      ,			UpperCamelCase		:      list[str] | None = None )  ->list[list[str]]:



			'''simple docstring'''







			lowerCamelCase__ :      List[str]								=		word_bank or []
			# create a table
			lowerCamelCase__ :      int								=		len(UpperCamelCase ) + 1

			lowerCamelCase__ :      list[list[list[str]]]								=		[]
			for _ in range(UpperCamelCase ):
						table.append([] )
			# seed value
			lowerCamelCase__ :      Tuple								=		[[]]  # because empty string has empty combination

			# iterate through the indices
			for i in range(UpperCamelCase ):
						# condition
						if table[i] != []:
									for word in word_bank:
												# slice condition
												if target[i : i + len(UpperCamelCase )] == word:
															lowerCamelCase__ :      list[list[str]]								=		[
															    [word, *way] for way in table[i]
															]
															# adds the word to every combination the current position holds
															# now,push that combination to the table[i+len(word)]
															table[i + len(UpperCamelCase )] += new_combinations

    # combinations are in reverse order so reverse for better output
			for combination in table[len(UpperCamelCase )]:
						combination.reverse()

			return table[len(UpperCamelCase )]


if __name__ == "__main__":
				print(all_construct('''jwajalapa''', ['''jwa''', '''j''', '''w''', '''a''', '''la''', '''lapa''']))
				print(all_construct('''rajamati''', ['''s''', '''raj''', '''amat''', '''raja''', '''ma''', '''i''', '''t''']))
				print(
				    all_construct(
				        '''hexagonosaurus''',
				        ['''h''', '''ex''', '''hex''', '''ag''', '''ago''', '''ru''', '''auru''', '''rus''', '''go''', '''no''', '''o''', '''s'''],
				    )
				)



