





def    __UpperCAmelCase(      lowercase_      ):
       if not head:
              return True
       # split the list to two parts
       _lowerCamelCase,  _lowerCamelCase							:     Optional[int]	=		head.next, head
       while fast and fast.next:
              _lowerCamelCase							:     Tuple	=		fast.next.next
              _lowerCamelCase							:     Tuple	=		slow.next
       _lowerCamelCase							:     Union[str, Any]	=		slow.next
       _lowerCamelCase							:     int	=		None  # Don't forget here! But forget still works!
       # reverse the second part
       _lowerCamelCase							:     Optional[Any]	=		None
       while second:
              _lowerCamelCase							:     Optional[Any]	=		second.next
              _lowerCamelCase							:     Dict	=		node
              _lowerCamelCase							:     List[Any]	=		second
              _lowerCamelCase							:     Optional[int]	=		nxt
       # compare two parts
       # second part has the same or one less node
       while node:
              if node.val != head.val:
                     return False
              _lowerCamelCase							:     Tuple	=		node.next
              _lowerCamelCase							:     Optional[Any]	=		head.next
       return True




def    __UpperCAmelCase(      lowercase_      ):
       if not head or not head.next:
              return True

       # 1. Get the midpoint (slow)
       _lowerCamelCase							:     Any	=		head
       while fast and fast.next:
              _lowerCamelCase,  _lowerCamelCase							:     List[Any]	=		fast.next.next, slow.next

       # 2. Push the second half into the stack
       _lowerCamelCase							:     Optional[Any]	=		[slow.val]
       while slow.next:
              _lowerCamelCase							:     int	=		slow.next
              stack.append(slow.val      )

       # 3. Comparison
       while stack:
              if stack.pop() != cur.val:
                     return False
              _lowerCamelCase							:     List[str]	=		cur.next

       return True




def    __UpperCAmelCase(      lowercase_      ):
       if not head or not head.next:
              return True
       _lowerCamelCase							:     Union[str, Any]	=		{}
       _lowerCamelCase							:     int	=		0
       while head:
              if head.val in d:
                     d[head.val].append(lowercase_      )
              else:
                     _lowerCamelCase							:     Tuple	=		[pos]
              _lowerCamelCase							:     int	=		head.next
              pos += 1
       _lowerCamelCase							:     Union[str, Any]	=		pos - 1
       _lowerCamelCase							:     List[str]	=		0
       for v in d.values():
              if len(lowercase_      ) % 2 != 0:
                     middle += 1
              else:
                     _lowerCamelCase							:     Optional[Any]	=		0
                     for i in range(0 ,    len(lowercase_      )      ):
                            if v[i] + v[len(lowercase_      ) - 1 - step] != checksum:
                                   return False
                            step += 1
              if middle > 1:
                     return False
       return True








def    __UpperCAmelCase(      lowercase_      ):
       # if the collection is empty, returns empty
       if collection == []:
              return []

       # get some information about the collection
       _lowerCamelCase							:     Tuple	=		len(lowercase_      )
       _lowerCamelCase							:     List[str]	=		max(lowercase_      )
       _lowerCamelCase							:     Any	=		min(lowercase_      )

       # create the counting array
       _lowerCamelCase							:     str	=		coll_max + 1 - coll_min
       _lowerCamelCase							:     Union[str, Any]	=		[0] * counting_arr_length

       # count how much a number appears in the collection
       for number in collection:
              counting_arr[number - coll_min] += 1

       # sum each position with it's predecessors. now, counting_arr[i] tells
       # us how many elements <= i has in the collection
       for i in range(1 ,    lowercase_      ):
              _lowerCamelCase							:     Union[str, Any]	=		counting_arr[i] + counting_arr[i - 1]

       # create the output collection
       _lowerCamelCase							:     Dict	=		[0] * coll_len

       # place the elements in the output, respecting the original order (stable
       # sort) from end to begin, updating counting_arr
       for i in reversed(range(0 ,    lowercase_      )      ):
              _lowerCamelCase							:     Union[str, Any]	=		collection[i]
              counting_arr[collection[i] - coll_min] -= 1

       return ordered




def    __UpperCAmelCase(      lowercase_      ):
       return "".join([chr(lowercase_      ) for i in counting_sort([ord(lowercase_      ) for c in string]      )]      )


if __name__ == "__main__":
       # Test string sort
       assert counting_sort_string('thisisthestring') == "eghhiiinrsssttt"

       _lowerCamelCase			       =      input('Enter numbers separated by a comma:\n').strip()
       _lowerCamelCase			       =      [int(item) for item in user_input.split(',')]
       print(counting_sort(unsorted))

