"""simple docstring"""






from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass


@dataclass
class 					UpperCAmelCase		:



    """simple docstring"""

    _UpperCAmelCase			:int
    _UpperCAmelCase			:TreeNode | None							=				None
    _UpperCAmelCase			:TreeNode | None							=				None



def SCREAMING_SNAKE_CASE__    (     )						->						TreeNode:
   return TreeNode(3 ,					TreeNode(9				) ,					TreeNode(2_0 ,					TreeNode(1_5				) ,					TreeNode(7				)				)				)



def SCREAMING_SNAKE_CASE__    (     __UpperCAmelCase				)						->						list[int]:

   def depth_first_search(
       __UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase				) -> None:
      if not root:
         return

      if depth == len(__UpperCAmelCase				):
         right_view.append(root.val				)

      depth_first_search(root.right ,					depth + 1 ,					__UpperCAmelCase				)
      depth_first_search(root.left ,					depth + 1 ,					__UpperCAmelCase				)

   lowercase__:     list      =   []
   if not root:
      return right_view

   depth_first_search(__UpperCAmelCase ,					0 ,					__UpperCAmelCase				)
   return right_view



def SCREAMING_SNAKE_CASE__    (     __UpperCAmelCase				)						->						list[int]:

   def depth_first_search(
       __UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase				) -> None:
      if not root:
         return

      if depth == len(__UpperCAmelCase				):
         left_view.append(root.val				)

      depth_first_search(root.left ,					depth + 1 ,					__UpperCAmelCase				)
      depth_first_search(root.right ,					depth + 1 ,					__UpperCAmelCase				)

   lowercase__:     list      =   []
   if not root:
      return left_view

   depth_first_search(__UpperCAmelCase ,					0 ,					__UpperCAmelCase				)
   return left_view



def SCREAMING_SNAKE_CASE__    (     __UpperCAmelCase				)						->						list[int]:

   def breadth_first_search(__UpperCAmelCase ,					__UpperCAmelCase				) -> None:
      lowercase__:     Optional[int]      =   [(root, 0)]
      lowercase__:     Dict      =   defaultdict(__UpperCAmelCase				)

      while queue:
         lowercase__:     Dict      =   queue.pop(0				)
         lowercase__,				lowercase__:     Optional[int]      =   first

         lookup[hd].append(node.val				)

         if node.left:
            queue.append((node.left, hd - 1)				)
         if node.right:
            queue.append((node.right, hd + 1)				)

      for pair in sorted(lookup.items() ,					key=lambda __UpperCAmelCase				: each[0]				):
         top_view.append(pair[1][0]				)

   lowercase__:     list      =   []
   if not root:
      return top_view

   breadth_first_search(__UpperCAmelCase ,					__UpperCAmelCase				)
   return top_view



def SCREAMING_SNAKE_CASE__    (     __UpperCAmelCase				)						->						list[int]:
   from collections import defaultdict

   def breadth_first_search(__UpperCAmelCase ,					__UpperCAmelCase				) -> None:
      lowercase__:     str      =   [(root, 0)]
      lowercase__:     List[Any]      =   defaultdict(__UpperCAmelCase				)

      while queue:
         lowercase__:     Optional[Any]      =   queue.pop(0				)
         lowercase__,				lowercase__:     Optional[Any]      =   first
         lookup[hd].append(node.val				)

         if node.left:
            queue.append((node.left, hd - 1)				)
         if node.right:
            queue.append((node.right, hd + 1)				)

      for pair in sorted(lookup.items() ,					key=lambda __UpperCAmelCase				: each[0]				):
         bottom_view.append(pair[1][-1]				)

   lowercase__:     list      =   []
   if not root:
      return bottom_view

   breadth_first_search(__UpperCAmelCase ,					__UpperCAmelCase				)
   return bottom_view


if __name__ == "__main__":
       import doctest

       doctest.testmod()

"""simple docstring"""






def SCREAMING_SNAKE_CASE__    (     __UpperCAmelCase				)						->						Optional[int]:
   lowercase__:     str      =   [7_0_1, 3_0_1, 1_3_2, 5_7, 2_3, 1_0, 4, 1]
   for gap in gaps:
      for i in range(__UpperCAmelCase ,					len(__UpperCAmelCase				)				):
         lowercase__:     Any      =   collection[i]
         lowercase__:     Tuple      =   i
         while j >= gap and collection[j - gap] > insert_value:
            lowercase__:     List[str]      =   collection[j - gap]
            j -= gap
         if j != i:
            lowercase__:     List[str]      =   insert_value
   return collection


if __name__ == "__main__":
       from doctest import testmod

       testmod()
       __A         =				input("Enter numbers separated by a comma:\n").strip()
       __A         =				[int(item) for item in user_input.split(",")]
       print(shell_sort(unsorted))
