

class __UpperCamelCase     :






					'''simple docstring'''



					def __init__(				self				,      lowerCamelCase__				,      lowerCamelCase__=None				,      lowerCamelCase__=None						):
						UpperCAmelCase__:	Optional[int]									= data
						UpperCAmelCase__:	List[Any]									= previous
						UpperCAmelCase__:	Optional[Any]									= next_node





					def __str__(				self						):
						return F"{self.data}"





					def    _UpperCAmelCase    (				self						):
						return self.data





					def    _UpperCAmelCase    (				self						):
						return self.next





					def    _UpperCAmelCase    (				self						):
						return self.previous

class __UpperCamelCase     :






					'''simple docstring'''



					def __init__(				self				,      lowerCamelCase__						):
						UpperCAmelCase__:	int									= head





					def __iter__(				self						):
						return self





					def    _UpperCAmelCase    (				self						):
						if not self.current:
							raise StopIteration
						else:
							UpperCAmelCase__:	Optional[int]									= self.current.get_data()
							UpperCAmelCase__:	List[str]									= self.current.get_next()
							return value

class __UpperCamelCase     :






					'''simple docstring'''



					def __init__(				self						):
						UpperCAmelCase__:	Dict									= None  # First node in list
						UpperCAmelCase__:	Dict									= None  # Last node in list





					def __str__(				self						):
						UpperCAmelCase__:	Optional[int]									= self.head
						UpperCAmelCase__:	Any									= []
						while current is not None:
							nodes.append(current.get_data()						)
							UpperCAmelCase__:	Tuple									= current.get_next()
						return " ".join(str(lowerCamelCase__						) for node in nodes						)





					def __contains__(				self				,      lowerCamelCase__						):
						UpperCAmelCase__:	Optional[Any]									= self.head
						while current:
							if current.get_data() == value:
								return True
							UpperCAmelCase__:	Union[str, Any]									= current.get_next()
						return False





					def __iter__(				self						):
						return LinkedListIterator(self.head						)





					def    _UpperCAmelCase    (				self						):
						if self.head:
							return self.head.get_data()
						return None





					def    _UpperCAmelCase    (				self						):
						if self.tail:
							return self.tail.get_data()
						return None





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						if self.head is None:
							UpperCAmelCase__:	Optional[Any]									= node
							UpperCAmelCase__:	Any									= node
						else:
							self.insert_before_node(self.head				,      lowerCamelCase__						)





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						if self.head is None:
							self.set_head(lowerCamelCase__						)
						else:
							self.insert_after_node(self.tail				,      lowerCamelCase__						)





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						UpperCAmelCase__:	Any									= Node(lowerCamelCase__						)
						if self.head is None:
							self.set_head(lowerCamelCase__						)
						else:
							self.set_tail(lowerCamelCase__						)





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__				,      lowerCamelCase__						):
						UpperCAmelCase__:	Optional[int]									= node
						UpperCAmelCase__:	Optional[int]									= node.previous

						if node.get_previous() is None:
							UpperCAmelCase__:	int									= node_to_insert
						else:
							UpperCAmelCase__:	Any									= node_to_insert

						UpperCAmelCase__:	Dict									= node_to_insert





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__				,      lowerCamelCase__						):
						UpperCAmelCase__:	int									= node
						UpperCAmelCase__:	str									= node.next

						if node.get_next() is None:
							UpperCAmelCase__:	Optional[Any]									= node_to_insert
						else:
							UpperCAmelCase__:	Union[str, Any]									= node_to_insert

						UpperCAmelCase__:	Tuple									= node_to_insert





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__				,      lowerCamelCase__						):
						UpperCAmelCase__:	Tuple									= 1
						UpperCAmelCase__:	str									= Node(lowerCamelCase__						)
						UpperCAmelCase__:	Optional[int]									= self.head
						while node:
							if current_position == position:
								self.insert_before_node(lowerCamelCase__				,      lowerCamelCase__						)
								return
							current_position += 1
							UpperCAmelCase__:	List[Any]									= node.next
						self.insert_after_node(self.tail				,      lowerCamelCase__						)





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						UpperCAmelCase__:	Union[str, Any]									= self.head
						while node:
							if node.get_data() == item:
								return node
							UpperCAmelCase__:	Dict									= node.get_next()
						raise Exception("Node not found"						)





					def    _UpperCAmelCase    (				self				,      lowerCamelCase__						):
						if (node := self.get_node(lowerCamelCase__						)) is not None:
							if node == self.head:
								UpperCAmelCase__:	str									= self.head.get_next()

							if node == self.tail:
								UpperCAmelCase__:	int									= self.tail.get_previous()

							self.remove_node_pointers(lowerCamelCase__						)





					@staticmethod
					def    _UpperCAmelCase    (				lowerCamelCase__						):
						if node.get_next():
							UpperCAmelCase__:	Tuple									= node.previous

						if node.get_previous():
							UpperCAmelCase__:	List[Any]									= node.next

						UpperCAmelCase__:	Tuple									= None
						UpperCAmelCase__:	str									= None





					def    _UpperCAmelCase    (				self						):
						return self.head is None



def 			_A	(      ):
	pass


if __name__ == "__main__":
					import doctest

					doctest.testmod()


def 			_A	(      SCREAMING_SNAKE_CASE      ):
	stooge(SCREAMING_SNAKE_CASE	,0	,len(SCREAMING_SNAKE_CASE      ) - 1      )
	return arr



def 			_A	(      SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE      ):
	if i >= h:
		return

	# If first element is smaller than the last then swap them
	if arr[i] > arr[h]:
		UpperCAmelCase__							,						UpperCAmelCase__:	int									= arr[h], arr[i]

	# If there are more than 2 elements in the array
	if h - i + 1 > 2:
		UpperCAmelCase__:	str									= (int)((h - i + 1) / 3      )

		# Recursively sort first 2/3 elements
		stooge(SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE	,(h - t)      )

		# Recursively sort last 2/3 elements
		stooge(SCREAMING_SNAKE_CASE	,i + t	,(SCREAMING_SNAKE_CASE)      )

		# Recursively sort first 2/3 elements
		stooge(SCREAMING_SNAKE_CASE	,SCREAMING_SNAKE_CASE	,(h - t)      )


if __name__ == "__main__":
					_lowerCAmelCase  :      List[str]			 =input("""Enter numbers separated by a comma:\n""").strip()
					_lowerCAmelCase  :      Any			 =[int(item) for item in user_input.split(""",""")]
					print(stooge_sort(unsorted))