



from __future__ import annotations

from collections.abc import Iterable





class 		UpperCAmelCase    :





   def __init__(						self							,  _lowerCAmelCase							,  _lowerCAmelCase      ):
         _lowerCAmelCase      , _lowerCAmelCase			      =	float(_lowerCAmelCase      ), float(_lowerCAmelCase      )





   def __eq__(						self							,  _lowerCAmelCase      ):
         return self.x == other.x and self.y == other.y





   def __ne__(						self							,  _lowerCAmelCase      ):
         return not self == other





   def __gt__(						self							,  _lowerCAmelCase      ):
         if self.x > other.x:
               return True
         elif self.x == other.x:
               return self.y > other.y
         return False





   def __lt__(						self							,  _lowerCAmelCase      ):
         return not self > other





   def __ge__(						self							,  _lowerCAmelCase      ):
         if self.x > other.x:
               return True
         elif self.x == other.x:
               return self.y >= other.y
         return False





   def __le__(						self							,  _lowerCAmelCase      ):
         if self.x < other.x:
               return True
         elif self.x == other.x:
               return self.y <= other.y
         return False





   def __repr__(						self      ):
         return F'''({self.x}, {self.y})'''





   def __hash__(						self      ):
         return hash(self.x      )






def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[Point] | list[list[float]] | Iterable[list[float]]  ,					)->list[Point]:
      _lowerCAmelCase			      =	[]
      if list_of_tuples:
            for p in list_of_tuples:
                  if isinstance(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					):
                        points.append(_SCREAMING_SNAKE_CASE					)
                  else:
                        try:
                              points.append(Point(p[0]  ,					p[1]					)					)
                        except (IndexError, TypeError):
                              print(
                                  f'''Ignoring deformed point {p}. All points'''
                                  ''' must have at least 2 coordinates.'''					)
      return points
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[Point] | list[list[float]]					)->list[Point]:

      if not hasattr(_SCREAMING_SNAKE_CASE  ,					'''__iter__'''					):
            _lowerCAmelCase			      =	f'''Expecting an iterable object but got an non-iterable type {points}'''
            raise ValueError(_SCREAMING_SNAKE_CASE					)

      if not points:
            _lowerCAmelCase			      =	f'''Expecting a list of points but got {points}'''
            raise ValueError(_SCREAMING_SNAKE_CASE					)

      return _construct_points(_SCREAMING_SNAKE_CASE					)
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						Point  ,					_SCREAMING_SNAKE_CASE :						Point  ,					_SCREAMING_SNAKE_CASE :						Point					)->float:
      _lowerCAmelCase			      =	(a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
      return det
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[Point]					)->list[Point]:
      _lowerCAmelCase			      =	sorted(_validate_input(_SCREAMING_SNAKE_CASE					)					)
      _lowerCAmelCase			      =	len(_SCREAMING_SNAKE_CASE					)
      _lowerCAmelCase			      =	set()

      for i in range(n - 1					):
            for j in range(i + 1  ,					_SCREAMING_SNAKE_CASE					):
                  _lowerCAmelCase			      =	_lowerCAmelCase			      =	False
                  _lowerCAmelCase			      =	True
                  for k in range(_SCREAMING_SNAKE_CASE					):
                        if k != i and k != j:
                              _lowerCAmelCase			      =	_det(points[i]  ,					points[j]  ,					points[k]					)

                              if det_k > 0:
                                    _lowerCAmelCase			      =	True
                              elif det_k < 0:
                                    _lowerCAmelCase			      =	True
                              else:
                                    # point[i], point[j], point[k] all lie on a straight line
                                    # if point[k] is to the left of point[i] or it's to the
                                    # right of point[j], then point[i], point[j] cannot be
                                    # part of the convex hull of A
                                    if points[k] < points[i] or points[k] > points[j]:
                                          _lowerCAmelCase			      =	False
                                          break

                        if points_left_of_ij and points_right_of_ij:
                              _lowerCAmelCase			      =	False
                              break

                  if ij_part_of_convex_hull:
                        convex_set.update([points[i], points[j]]					)

      return sorted(_SCREAMING_SNAKE_CASE					)
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[Point]					)->list[Point]:
      _lowerCAmelCase			      =	sorted(_validate_input(_SCREAMING_SNAKE_CASE					)					)
      _lowerCAmelCase			      =	len(_SCREAMING_SNAKE_CASE					)

      # divide all the points into an upper hull and a lower hull
      # the left most point and the right most point are definitely
      # members of the convex hull by definition.
      # use these two anchors to divide all the points into two hulls,
      # an upper hull and a lower hull.

      # all points to the left (above) the line joining the extreme points belong to the
      # upper hull
      # all points to the right (below) the line joining the extreme points below to the
      # lower hull
      # ignore all points on the line joining the extreme points since they cannot be
      # part of the convex hull

      _lowerCAmelCase			      =	points[0]
      _lowerCAmelCase			      =	points[n - 1]

      _lowerCAmelCase			      =	{left_most_point, right_most_point}
      _lowerCAmelCase			      =	[]
      _lowerCAmelCase			      =	[]

      for i in range(1  ,					n - 1					):
            _lowerCAmelCase			      =	_det(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					points[i]					)

            if det > 0:
                  upper_hull.append(points[i]					)
            elif det < 0:
                  lower_hull.append(points[i]					)

      _construct_hull(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
      _construct_hull(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)

      return sorted(_SCREAMING_SNAKE_CASE					)
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[Point]  ,					_SCREAMING_SNAKE_CASE :						Point  ,					_SCREAMING_SNAKE_CASE :						Point  ,					_SCREAMING_SNAKE_CASE :						set[Point]					)->None:
      if points:
            _lowerCAmelCase			      =	None
            _lowerCAmelCase			      =	float('''-inf'''					)
            _lowerCAmelCase			      =	[]

            for p in points:
                  _lowerCAmelCase			      =	_det(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)

                  if det > 0:
                        candidate_points.append(_SCREAMING_SNAKE_CASE					)

                        if det > extreme_point_distance:
                              _lowerCAmelCase			      =	det
                              _lowerCAmelCase			      =	p

            if extreme_point:
                  _construct_hull(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
                  convex_set.add(_SCREAMING_SNAKE_CASE					)
                  _construct_hull(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[Point]					)->list[Point]:
      _lowerCAmelCase			      =	sorted(_validate_input(_SCREAMING_SNAKE_CASE					)					)
      _lowerCAmelCase			      =	len(_SCREAMING_SNAKE_CASE					)

      _lowerCAmelCase			      =	points[:2]
      for i in range(2  ,					_SCREAMING_SNAKE_CASE					):
            _lowerCAmelCase			      =	_det(convex_hull[1]  ,					convex_hull[0]  ,					points[i]					)
            if det > 0:
                  convex_hull.insert(0  ,					points[i]					)
                  break
            elif det < 0:
                  convex_hull.append(points[i]					)
                  break
            else:
                  _lowerCAmelCase			      =	points[i]
      i += 1

      for j in range(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					):
            if (
                _det(convex_hull[0]  ,					convex_hull[-1]  ,					points[j]					) > 0
                and _det(convex_hull[-1]  ,					convex_hull[0]  ,					points[1]					) < 0
            ):
                  # The point lies within the convex hull
                  continue

            convex_hull.insert(0  ,					points[j]					)
            convex_hull.append(points[j]					)
            while _det(convex_hull[0]  ,					convex_hull[1]  ,					convex_hull[2]					) >= 0:
                  del convex_hull[1]
            while _det(convex_hull[-1]  ,					convex_hull[-2]  ,					convex_hull[-3]					) <= 0:
                  del convex_hull[-2]

    # `convex_hull` is contains the convex hull in circular order
      return sorted(convex_hull[1:] if len(_SCREAMING_SNAKE_CASE					) > 3 else convex_hull					)
def 				UpperCAmelCase__		(					)->List[str]:
      _lowerCAmelCase			      =	[
          (0, 3),
          (2, 2),
          (1, 1),
          (2, 1),
          (3, 0),
          (0, 0),
          (3, 3),
          (2, -1),
          (2, -4),
          (1, -3),
      ]
      # the convex set of points is
      # [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
      _lowerCAmelCase			      =	convex_hull_bf(_SCREAMING_SNAKE_CASE					)

      _lowerCAmelCase			      =	convex_hull_recursive(_SCREAMING_SNAKE_CASE					)
      assert results_bf == results_recursive

      _lowerCAmelCase			      =	convex_hull_melkman(_SCREAMING_SNAKE_CASE					)
      assert results_bf == results_melkman

      print(_SCREAMING_SNAKE_CASE					)


if __name__ == "__main__":
    main()




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))