


from heapq import heappop, heappush

import numpy as np


def __lowercase     (      lowerCamelCase_  :      np.ndarray						,					lowerCamelCase_  :      tuple[int, int]						,					lowerCamelCase_  :      tuple[int, int]						,					lowerCamelCase_  :      bool						,					):
				SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     							=				grid.shape
				SCREAMING_SNAKE_CASE__     							=				[-1, 1, 0, 0]
				SCREAMING_SNAKE_CASE__     							=				[0, 0, -1, 1]
				if allow_diagonal:
								dx += [-1, -1, 1, 1]
								dy += [-1, 1, -1, 1]

				SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     							=				[(0, source)], set()
				SCREAMING_SNAKE_CASE__     							=				np.full((rows, cols)						,					np.inf  )
				SCREAMING_SNAKE_CASE__     							=				0
				SCREAMING_SNAKE_CASE__     							=				np.empty((rows, cols)						,					dtype=lowerCamelCase_  )
				SCREAMING_SNAKE_CASE__     							=				None

				while queue:
								((SCREAMING_SNAKE_CASE__)							,      (SCREAMING_SNAKE_CASE__))     							=				heappop(lowerCamelCase_  )
								if (x, y) in visited:
												continue
								visited.add((x, y)  )

								if (x, y) == destination:
												SCREAMING_SNAKE_CASE__     							=				[]
												while (x, y) != source:
																path.append((x, y)  )
																SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     							=				predecessors[x, y]
												path.append(lowerCamelCase_  )  # add the source manually
												path.reverse()
												return matrix[destination], path

								for i in range(len(lowerCamelCase_  )  ):
												SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     							=				x + dx[i], y + dy[i]
												if 0 <= nx < rows and 0 <= ny < cols:
																SCREAMING_SNAKE_CASE__     							=				grid[nx][ny]
																if next_node == 1 and matrix[nx, ny] > dist + 1:
																				heappush(lowerCamelCase_						,					(dist + 1, (nx, ny))  )
																				SCREAMING_SNAKE_CASE__     							=				dist + 1
																				SCREAMING_SNAKE_CASE__     							=				(x, y)

				return np.inf, []


if __name__ == "__main__":
	import doctest

	doctest.testmod()




"""simple docstring"""






from __future__ import annotations


def __lowercase     (      lowerCamelCase_  :      list						,					lowerCamelCase_  :      int						,					lowerCamelCase_  :      int						,					lowerCamelCase_  :      int  ):
				SCREAMING_SNAKE_CASE__     							=				[]
				SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     							=				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  )  )
				SCREAMING_SNAKE_CASE__     							=				result + left + right
				return input_list


def __lowercase     (      lowerCamelCase_  :      list  ):
				if len(lowerCamelCase_  ) <= 1:
								return input_list
				SCREAMING_SNAKE_CASE__     							=				list(lowerCamelCase_  )

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

				return input_list


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