




"""simple docstring"""





import heapq
import sys

import numpy as np

lowerCamelCase      =		tuple[int, int]
class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Union[str, Any]					)				->		Optional[int]:


             '''simple docstring'''




             UpperCAmelCase_    				=							[]
             UpperCAmelCase_    				=							set()



       def   lowercase__       (							self    :						Union[str, Any]					)				->		Optional[int]:


             '''simple docstring'''




             if not self.empty():
                   return self.elements[0][0]
             else:
                   return float("inf"					)



       def   lowercase__       (							self    :						str					)				->		List[Any]:


             '''simple docstring'''




             return len(self.elements					) == 0



       def   lowercase__       (							self    :						Union[str, Any]	,       _UpperCAmelCase    :						List[Any]	,       _UpperCAmelCase    :						Optional[int]					)				->		Union[str, Any]:


             '''simple docstring'''




             if item not in self.set:
                   heapq.heappush(self.elements	,       (priority, item)					)
                   self.set.add(_UpperCAmelCase					)
             else:
                   # update
                   # print("update", item)
                   UpperCAmelCase_    				=							[]
                   ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							heapq.heappop(self.elements					)
                   while x != item:
                         temp.append((pri, x)					)
                         ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							heapq.heappop(self.elements					)
                   temp.append((priority, item)					)
                   for pro, xxx in temp:
                         heapq.heappush(self.elements	,       (pro, xxx)					)



       def   lowercase__       (							self    :						Optional[int]	,       _UpperCAmelCase    :						Dict					)				->		Optional[Any]:


             '''simple docstring'''




             if item in self.set:
                   self.set.remove(_UpperCAmelCase					)
                   UpperCAmelCase_    				=							[]
                   ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							heapq.heappop(self.elements					)
                   while x != item:
                         temp.append((pro, x)					)
                         ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							heapq.heappop(self.elements					)
                   for prito, yyy in temp:
                         heapq.heappush(self.elements	,       (prito, yyy)					)



       def   lowercase__       (							self    :						int					)				->		Optional[Any]:


             '''simple docstring'''




             return self.elements[0][1]







       def   lowercase__       (							self    :						Optional[int]					)				->		Union[str, Any]:


             '''simple docstring'''




             ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							heapq.heappop(self.elements					)
             self.set.remove(_UpperCAmelCase					)
             return (priority, item)



def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      # euclidean distance
      UpperCAmelCase_    				=							np.array(lowerCAmelCase__   )
      UpperCAmelCase_    				=							np.array(lowerCAmelCase__   )
      return np.linalg.norm(a - b   )
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      # integer division by time variable
      return consistent_heuristic(lowerCAmelCase__			,    lowerCAmelCase__   ) // t
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      # manhattan distance
      return abs(p[0] - goal[0]   ) + abs(p[1] - goal[1]   )
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							g_function[start] + Wa * heuristics[i](lowerCAmelCase__			,    lowerCAmelCase__   )
      return ans
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							np.chararray((n, n)   )
      for i in range(lowerCAmelCase__   ):
            for j in range(lowerCAmelCase__   ):
                  UpperCAmelCase_    				=							"*"

      for i in range(lowerCAmelCase__   ):
            for j in range(lowerCAmelCase__   ):
                  if (j, (n - 1) - i) in blocks:
                        UpperCAmelCase_    				=							"#"

      UpperCAmelCase_    				=							"-"
      UpperCAmelCase_    				=							back_pointer[goal]
      while x != start:
            ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							x
            # print(x)
            UpperCAmelCase_    				=							"-"
            UpperCAmelCase_    				=							back_pointer[x]
      UpperCAmelCase_    				=							"-"

      for i in range(lowerCAmelCase__   ):
            for j in range(lowerCAmelCase__   ):
                  if (i, j) == (0, n - 1):
                        print(grid[i][j]			,    end=" "   )
                        print("<-- End position"			,    end=" "   )
                  else:
                        print(grid[i][j]			,    end=" "   )
            print()
      print("^"   )
      print("Start position"   )
      print()
      print("# is an obstacle"   )
      print("- is the path taken by algorithm"   )
      print("PATH TAKEN BY THE ALGORITHM IS:-"   )
      UpperCAmelCase_    				=							back_pointer[goal]
      while x != start:
            print(lowerCAmelCase__			,    end=" "   )
            UpperCAmelCase_    				=							back_pointer[x]
      print(lowerCAmelCase__   )
      sys.exit()
def      a__			(   lowerCAmelCase__   ):
      if p[0] < 0 or p[0] > n - 1:
            return False
      if p[1] < 0 or p[1] > n - 1:
            return False
      return True
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    ):
      for itera in range(lowerCAmelCase__   ):
            open_list[itera].remove_element(lowerCAmelCase__   )
      # print("s", s)
      # print("j", j)
      ((UpperCAmelCase_)				,					(UpperCAmelCase_))    				=							s
      UpperCAmelCase_    				=							(x - 1, y)
      UpperCAmelCase_    				=							(x + 1, y)
      UpperCAmelCase_    				=							(x, y + 1)
      UpperCAmelCase_    				=							(x, y - 1)

      for neighbours in [left, right, up, down]:
            if neighbours not in blocks:
                  if valid(lowerCAmelCase__   ) and neighbours not in visited:
                        # print("neighbour", neighbours)
                        visited.add(lowerCAmelCase__   )
                        UpperCAmelCase_    				=							-1
                        UpperCAmelCase_    				=							float("inf"   )

                  if valid(lowerCAmelCase__   ) and g_function[neighbours] > g_function[s] + 1:
                        UpperCAmelCase_    				=							g_function[s] + 1
                        UpperCAmelCase_    				=							s
                        if neighbours not in close_list_anchor:
                              open_list[0].put(lowerCAmelCase__			,    key(lowerCAmelCase__			,    0			,    lowerCAmelCase__			,    lowerCAmelCase__   )   )
                              if neighbours not in close_list_inad:
                                    for var in range(1			,    lowerCAmelCase__   ):
                                          if key(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ) <= Wa * key(
                                              lowerCAmelCase__			,    0			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
                                                open_list[j].put(
                                                    lowerCAmelCase__			,    key(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )   )
def      a__			(   ):
      UpperCAmelCase_    				=							[]
      for x in range(1			,    5   ):
            for y in range(1			,    6   ):
                  some_list.append((x, y)   )

      for x in range(15			,    20   ):
            some_list.append((x, 17)   )

      for x in range(10			,    19   ):
            for y in range(1			,    15   ):
                  some_list.append((x, y)   )

    # L block
      for x in range(1			,    4   ):
            for y in range(12			,    19   ):
                  some_list.append((x, y)   )
      for x in range(3			,    13   ):
            for y in range(16			,    19   ):
                  some_list.append((x, y)   )
      return some_list


lowerCamelCase      =		{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

lowerCamelCase      =		[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
lowerCamelCase      =		make_common_ground()


lowerCamelCase      =		blocks_blk
# hyper parameters
lowerCamelCase      =		1
lowerCamelCase      =		1
lowerCamelCase      =		20
lowerCamelCase      =		3  # one consistent and two other inconsistent

# start and end destination
lowerCamelCase      =		(0, 0)
lowerCamelCase      =		(n - 1, n - 1)

lowerCamelCase      =		1
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							{start: 0, goal: float("inf"   )}
      UpperCAmelCase_    				=							{start: -1, goal: -1}
      UpperCAmelCase_    				=							[]
      UpperCAmelCase_    				=							set()

      for i in range(lowerCAmelCase__   ):
            open_list.append(PriorityQueue()   )
            open_list[i].put(lowerCAmelCase__			,    key(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )   )

      UpperCAmelCase_    				=							[]
      UpperCAmelCase_    				=							[]
      while open_list[0].minkey() < float("inf"   ):
            for i in range(1			,    lowerCAmelCase__   ):
                  # print(open_list[0].minkey(), open_list[i].minkey())
                  if open_list[i].minkey() <= Wa * open_list[0].minkey():
                        global t
                        t += 1
                        if g_function[goal] <= open_list[i].minkey():
                              if g_function[goal] < float("inf"   ):
                                    do_something(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )
                        else:
                              UpperCAmelCase_				,					UpperCAmelCase_    				=							open_list[i].top_show()
                              visited.add(lowerCAmelCase__   )
                              expand_state(
                                  lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    )
                              close_list_inad.append(lowerCAmelCase__   )
                  else:
                        if g_function[goal] <= open_list[0].minkey():
                              if g_function[goal] < float("inf"   ):
                                    do_something(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )
                        else:
                              UpperCAmelCase_    				=							open_list[0].top_show()
                              visited.add(lowerCAmelCase__   )
                              expand_state(
                                  lowerCAmelCase__			,    0			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    )
                              close_list_anchor.append(lowerCAmelCase__   )
      print("No path found to goal"   )
      print()
      for i in range(n - 1			,    -1			,    -1   ):
            for j in range(lowerCAmelCase__   ):
                  if (j, i) in blocks:
                        print("#"			,    end=" "   )
                  elif (j, i) in back_pointer:
                        if (j, i) == (n - 1, n - 1):
                              print("*"			,    end=" "   )
                        else:
                              print("-"			,    end=" "   )
                  else:
                        print("*"			,    end=" "   )
                  if (j, i) == (n - 1, n - 1):
                        print("<-- End position"			,    end=" "   )
            print()
      print("^"   )
      print("Start position"   )
      print()
      print("# is an obstacle"   )
      print("- is the path taken by algorithm"   )


if __name__ == "__main__":
  multi_a_star(start, goal, n_heuristic)









"""simple docstring"""





from __future__ import annotations
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							[]
      UpperCAmelCase_				,					UpperCAmelCase_    				=							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   )   )
      UpperCAmelCase_    				=							result + left + right
      return input_list
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) <= 1:
            return input_list
      UpperCAmelCase_    				=							list(lowerCAmelCase__   )

      # iteration for two-way merging
      UpperCAmelCase_    				=							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__   ):
                  UpperCAmelCase_    				=							i
                  UpperCAmelCase_    				=							i + p - 1
                  UpperCAmelCase_    				=							(low + high + 1) // 2
                  UpperCAmelCase_    				=							merge(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )
            # final merge of last two parts
            if p * 2 >= len(lowerCAmelCase__   ):
                  UpperCAmelCase_    				=							i
                  UpperCAmelCase_    				=							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))




