






from __future__ import annotations





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case       ,			__snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       []
     __lowerCAmelCase      ,			__lowerCAmelCase             =       input_list[low:mid], input_list[mid : high + 1]
     while left and right:
          result.append((left if left[0] <= right[0] else right).pop(0							)							)
     __lowerCAmelCase             =       result + left + right
     return input_list





def    __lowerCAmelCase   (    __snake_case							):
     if len(__snake_case							) <= 1:
          return input_list
     __lowerCAmelCase             =       list(__snake_case							)

     # iteration for two-way merging
     __lowerCAmelCase             =       2
     while p <= len(__snake_case							):
          # getting low, high and middle value for merge-sort of single list
          for i in range(0       ,			len(__snake_case							)       ,			__snake_case							):
               __lowerCAmelCase             =       i
               __lowerCAmelCase             =       i + p - 1
               __lowerCAmelCase             =       (low + high + 1) // 2
               __lowerCAmelCase             =       merge(__snake_case       ,			__snake_case       ,			__snake_case       ,			__snake_case							)
          # final merge of last two parts
          if p * 2 >= len(__snake_case							):
               __lowerCAmelCase             =       i
               __lowerCAmelCase             =       merge(__snake_case       ,			0       ,			__snake_case       ,			len(__snake_case							) - 1							)
               break
          p *= 2

     return input_list


if __name__ == "__main__":
 lowerCamelCase      :       int    =						input('''Enter numbers separated by a comma:\n''').strip()
 if user_input == "":
  lowerCamelCase      :       Tuple    =						[]
 else:
  lowerCamelCase      :       Union[str, Any]    =						[int(item.strip()) for item in user_input.split(''',''')]
 print(iter_merge_sort(unsorted))














from __future__ import annotations





def    __lowerCAmelCase   (    __snake_case							):
     __lowerCAmelCase             =       len(__snake_case							)
     # We need to create solution object to save path.
     __lowerCAmelCase             =       [[0 for _ in range(__snake_case							)] for _ in range(__snake_case							)]
     __lowerCAmelCase             =       run_maze(__snake_case       ,			0       ,			0       ,			__snake_case							)
     if solved:
          print("\n".join(str(__snake_case							) for row in solutions							)							)
     else:
          print("No solution exists!"							)
     return solved





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case       ,			__snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       len(__snake_case							)
     # Final check point.
     if i == j == (size - 1):
          __lowerCAmelCase             =       1
          return True

     __lowerCAmelCase             =       (not i < 0) and (not j < 0)  # Check lower bounds
     __lowerCAmelCase             =       (i < size) and (j < size)  # Check upper bounds

     if lower_flag and upper_flag:
          # check for already visited and block points.
          __lowerCAmelCase             =       (not solutions[i][j]) and (not maze[i][j])
          if block_flag:
               # check visited
               __lowerCAmelCase             =       1

               # check for directions
               if (
                   run_maze(__snake_case       ,			i + 1       ,			__snake_case       ,			__snake_case							)
                   or run_maze(__snake_case       ,			__snake_case       ,			j + 1       ,			__snake_case							)
                   or run_maze(__snake_case       ,			i - 1       ,			__snake_case       ,			__snake_case							)
                   or run_maze(__snake_case       ,			__snake_case       ,			j - 1       ,			__snake_case							)
               ):
                    return True

               __lowerCAmelCase             =       0
               return False
     return False


if __name__ == "__main__":
 import doctest

 doctest.testmod()






