




'''simple docstring'''







from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

_lowerCamelCase				:		Union[str, Any]				      =    TypeVar('T')
_lowerCamelCase				:		str				      =    TypeVar('U')





class 	lowerCamelCase_				(			Generic[T, U]				):




					'''simple docstring'''






					def __init__(       self,    __UpperCamelCase,    __UpperCamelCase					):
							_snake_case      			=			key
							_snake_case      			=			val
							_snake_case      			=			0
							_snake_case      			=			None
							_snake_case      			=			None






					def __repr__(       self					):
							return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
							    self.key,    self.val,    self.freq,    self.next is not None,    self.prev is not None					)





class 	lowerCamelCase_				(			Generic[T, U]				):




					'''simple docstring'''






					def __init__(       self					):
							_snake_case      			=			DoubleLinkedListNode(_lowerCAmelCase,    _lowerCAmelCase					)
							_snake_case      			=			DoubleLinkedListNode(_lowerCAmelCase,    _lowerCAmelCase					)
							_snake_case			,       _snake_case      			=			self.rear, self.head






					def __repr__(       self					):
							_snake_case      			=			["DoubleLinkedList"]
							_snake_case      			=			self.head
							while node.next is not None:
									rep.append(str(_lowerCAmelCase					)					)
									_snake_case      			=			node.next
							rep.append(str(self.rear					)					)
							return ",\n    ".join(_lowerCAmelCase					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							_snake_case      			=			self.rear.prev

							# All nodes other than self.head are guaranteed to have non-None previous
							assert previous is not None

							_snake_case      			=			node
							_snake_case      			=			previous
							_snake_case      			=			node
							_snake_case      			=			self.rear
							node.freq += 1
							self._position_node(_lowerCAmelCase					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):

							while node.prev is not None and node.prev.freq > node.freq:
									# swap node with previous node
									_snake_case      			=			node.prev

									_snake_case      			=			previous_node.prev
									_snake_case      			=			node.prev
									_snake_case      			=			previous_node
									_snake_case      			=			node






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):

							if node.prev is None or node.next is None:
									return None

							_snake_case      			=			node.next
							_snake_case      			=			node.prev
							_snake_case      			=			None
							_snake_case      			=			None
							return node





class 	lowerCamelCase_				(			Generic[T, U]				):




					'''simple docstring'''






					lowercase__       =					{}






					def __init__(       self,    __UpperCamelCase					):
							_snake_case      			=			DoubleLinkedList()
							_snake_case      			=			capacity
							_snake_case      			=			0
							_snake_case      			=			0
							_snake_case      			=			0
							_snake_case      			=			{}






					def __repr__(       self					):
							return (
							    f'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
							    f'''capacity={self.capacity}, current_size={self.num_keys})'''
							)






					def __contains__(       self,    __UpperCamelCase					):
							return key in self.cache






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):

							if key in self.cache:
									self.hits += 1
									_snake_case      			=			self.cache[key]
									_snake_case      			=			self.list.remove(self.cache[key]					)
									assert node == value_node

									# node is guaranteed not None because it is in self.cache
									assert node is not None
									self.list.add(_lowerCAmelCase					)
									return node.val
							self.miss += 1
							return None






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase,    __UpperCamelCase					):

							if key not in self.cache:
									if self.num_keys >= self.capacity:
											# delete first node when over capacity
											_snake_case      			=			self.list.head.next

											# guaranteed to have a non-None first node when num_keys > 0
											# explain to type checker via assertions
											assert first_node is not None
											assert first_node.key is not None
											assert self.list.remove(_lowerCAmelCase					) is not None
											# first_node guaranteed to be in list

											del self.cache[first_node.key]
											self.num_keys -= 1
									_snake_case      			=			DoubleLinkedListNode(_lowerCAmelCase,    _lowerCAmelCase					)
									self.list.add(self.cache[key]					)
									self.num_keys += 1

							else:
									_snake_case      			=			self.list.remove(self.cache[key]					)
									assert node is not None  # node guaranteed to be in list
									_snake_case      			=			value
									self.list.add(_lowerCAmelCase					)






					@classmethod
					def 							__SCREAMING_SNAKE_CASE      (       cls,    __UpperCamelCase = 128					):

							def cache_decorator_inner(__UpperCamelCase					) -> Callable[..., U]:
									def cache_decorator_wrapper(*__UpperCamelCase					) -> U:
											if func not in cls.decorator_function_to_instance_map:
													_snake_case      			=			LFUCache(_lowerCAmelCase					)

											_snake_case      			=			cls.decorator_function_to_instance_map[func].get(args[0]					)
											if result is None:
													_snake_case      			=			func(*_lowerCAmelCase					)
													cls.decorator_function_to_instance_map[func].put(args[0],    _lowerCAmelCase					)
											return result

									def cache_info() -> LFUCache[T, U]:
											return cls.decorator_function_to_instance_map[func]

									setattr(_lowerCAmelCase,    "cache_info",    _lowerCAmelCase					)  # noqa: B010

									return cache_decorator_wrapper

							return cache_decorator_inner


if __name__ == "__main__":
						import doctest

						doctest.testmod()










from __future__ import annotations

from random import randrange
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list					)->list:
      if len(_SCREAMING_SNAKE_CASE					) < 2:
            return collection
      _lowerCAmelCase			      =	randrange(len(_SCREAMING_SNAKE_CASE					)					)  # Use random element as pivot
      _lowerCAmelCase			      =	collection[pivot_index]
      _lowerCAmelCase			      =	[]  # All elements greater than pivot
      _lowerCAmelCase			      =	[]  # All elements less than or equal to pivot

      for element in collection[:pivot_index]:
            (greater if element > pivot else lesser).append(_SCREAMING_SNAKE_CASE					)

      for element in collection[pivot_index + 1 :]:
            (greater if element > pivot else lesser).append(_SCREAMING_SNAKE_CASE					)

      return [*quick_sort(_SCREAMING_SNAKE_CASE					), pivot, *quick_sort(_SCREAMING_SNAKE_CASE					)]


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