"""simple docstring"""



import heapq
import sys

import numpy as np

__A :     Optional[int]				       =				tuple[int, int]






class 	__lowerCAmelCase					:




    '''simple docstring'''






    def __init__(     self				:	Tuple							):
          A__	:      Tuple      =[]
          A__	:      Tuple      =set()





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





    def 					_UpperCAmelCase		(     self				:	int							):
          return len(self.elements							) == 0





    def 					_UpperCAmelCase		(     self				:	int					,				UpperCamelCase__				:	Dict					,				UpperCamelCase__				:	List[str]							):
          if item not in self.set:
                heapq.heappush(self.elements					,				(priority, item)							)
                self.set.add(__snake_case							)
          else:
                # update
                # print("update", item)
                A__	:      List[Any]      =[]
                (A__)	:      List[str]      =heapq.heappop(self.elements							)
                while x != item:
                      temp.append((pri, x)							)
                      (A__)	:      Union[str, Any]      =heapq.heappop(self.elements							)
                temp.append((priority, item)							)
                for pro, xxx in temp:
                      heapq.heappush(self.elements					,				(pro, xxx)							)





    def 					_UpperCAmelCase		(     self				:	List[Any]					,				UpperCamelCase__				:	str							):
          if item in self.set:
                self.set.remove(__snake_case							)
                A__	:      Optional[int]      =[]
                (A__)	:      Union[str, Any]      =heapq.heappop(self.elements							)
                while x != item:
                      temp.append((pro, x)							)
                      (A__)	:      Union[str, Any]      =heapq.heappop(self.elements							)
                for prito, yyy in temp:
                      heapq.heappush(self.elements					,				(prito, yyy)							)





    def 					_UpperCAmelCase		(     self				:	List[Any]							):
          return self.elements[0][1]





    def 					_UpperCAmelCase		(     self				:	Any							):
          (A__)	:      int      =heapq.heappop(self.elements							)
          self.set.remove(__snake_case							)
          return (priority, item)



def 		lowercase (       UpperCamelCase     :     List[str]       ,  UpperCamelCase     :     int		):





      """simple docstring"""
      A__	:      int      =np.array(SCREAMING_SNAKE_CASE__		)
      A__	:      List[str]      =np.array(SCREAMING_SNAKE_CASE__		)
      return np.linalg.norm(a - b		)



def 		lowercase (       UpperCamelCase     :     Dict       ,  UpperCamelCase     :     Tuple		):





      """simple docstring"""
      return consistent_heuristic(SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		) // t



def 		lowercase (       UpperCamelCase     :     Union[str, Any]       ,  UpperCamelCase     :     Optional[Any]		):





      """simple docstring"""
      return abs(p[0] - goal[0]		) + abs(p[1] - goal[1]		)



def 		lowercase (       UpperCamelCase     :     Optional[Any]       ,  UpperCamelCase     :     List[str]       ,  UpperCamelCase     :     Tuple       ,  UpperCamelCase     :     List[Any]		):





      """simple docstring"""
      A__	:      Optional[int]      =g_function[start] + Wa * heuristics[i](SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		)
      return ans



def 		lowercase (       UpperCamelCase     :     List[str]       ,  UpperCamelCase     :     List[Any]       ,  UpperCamelCase     :     Dict		):





      """simple docstring"""
      A__	:      Tuple      =np.chararray((n, n)		)
      for i in range(SCREAMING_SNAKE_CASE__		):
            for j in range(SCREAMING_SNAKE_CASE__		):
                  A__	:      List[str]      ="""*"""

      for i in range(SCREAMING_SNAKE_CASE__		):
            for j in range(SCREAMING_SNAKE_CASE__		):
                  if (j, (n - 1) - i) in blocks:
                        A__	:      List[str]      ="""#"""

      A__	:      Tuple      ="""-"""
      A__	:      int      =back_pointer[goal]
      while x != start:
            (A__)	:      str      =x
            # print(x)
            A__	:      str      ="""-"""
            A__	:      Any      =back_pointer[x]
      A__	:      Union[str, Any]      ="""-"""

      for i in range(SCREAMING_SNAKE_CASE__		):
            for j in range(SCREAMING_SNAKE_CASE__		):
                  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:-"		)
      A__	:      Union[str, Any]      =back_pointer[goal]
      while x != start:
            print(SCREAMING_SNAKE_CASE__       ,  end=" "		)
            A__	:      str      =back_pointer[x]
      print(SCREAMING_SNAKE_CASE__		)
      sys.exit()



def 		lowercase (       UpperCamelCase     :     Union[str, Any]		):





      """simple docstring"""





      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 		lowercase (       UpperCamelCase     :     Tuple       ,  UpperCamelCase     :     Dict       ,  UpperCamelCase     :     Optional[int]       ,  UpperCamelCase     :     str       ,  UpperCamelCase     :     Union[str, Any]       ,  UpperCamelCase     :     Tuple       ,  UpperCamelCase     :     Tuple       ,  UpperCamelCase     :     int       ,  ):





      """simple docstring"""





      for itera in range(SCREAMING_SNAKE_CASE__		):
            open_list[itera].remove_element(SCREAMING_SNAKE_CASE__		)
      # print("s", s)
      # print("j", j)
      (A__)	:      int      =s
      A__	:      Union[str, Any]      =(x - 1, y)
      A__	:      Optional[int]      =(x + 1, y)
      A__	:      List[str]      =(x, y + 1)
      A__	:      Any      =(x, y - 1)

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

                  if valid(SCREAMING_SNAKE_CASE__		) and g_function[neighbours] > g_function[s] + 1:
                        A__	:      Optional[Any]      =g_function[s] + 1
                        A__	:      Tuple      =s
                        if neighbours not in close_list_anchor:
                              open_list[0].put(SCREAMING_SNAKE_CASE__       ,  key(SCREAMING_SNAKE_CASE__       ,  0       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		)		)
                              if neighbours not in close_list_inad:
                                    for var in range(1       ,  SCREAMING_SNAKE_CASE__		):
                                          if key(SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		) <= Wa * key(
                                              SCREAMING_SNAKE_CASE__       ,  0       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		):
                                                open_list[j].put(
                                                    SCREAMING_SNAKE_CASE__       ,  key(SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		)		)



def 		lowercase (       ):





      """simple docstring"""
      A__	:      Optional[int]      =[]
      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


__A :     Optional[int]				       =				{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__A :     Union[str, Any]				       =				[
    (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),
]
__A :     Optional[int]				       =				make_common_ground()


__A :     List[Any]				       =				blocks_blk
# hyper parameters
__A :     Tuple				       =				1
__A :     Any				       =				1
__A :     Optional[int]				       =				20
__A :     Optional[int]				       =				3  # one consistent and two other inconsistent

# start and end destination
__A :     Any				       =				(0, 0)
__A :     List[str]				       =				(n - 1, n - 1)

__A :     Tuple				       =				1



def 		lowercase (       UpperCamelCase     :     Tuple       ,  UpperCamelCase     :     Union[str, Any]       ,  UpperCamelCase     :     Optional[int]		):





      """simple docstring"""
      A__	:      Optional[int]      ={start: 0, goal: float("inf"		)}
      A__	:      int      ={start: -1, goal: -1}
      A__	:      Any      =[]
      A__	:      Union[str, Any]      =set()

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

      A__	:      list[int]      =[]
      A__	:      list[int]      =[]
      while open_list[0].minkey() < float("inf"		):
            for i in range(1       ,  SCREAMING_SNAKE_CASE__		):
                  # 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(SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		)
                        else:
                              A__	:      Optional[int]      =open_list[i].top_show()
                              visited.add(SCREAMING_SNAKE_CASE__		)
                              expand_state(
                                  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  )
                              close_list_inad.append(SCREAMING_SNAKE_CASE__		)
                  else:
                        if g_function[goal] <= open_list[0].minkey():
                              if g_function[goal] < float("inf"		):
                                    do_something(SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__		)
                        else:
                              A__	:      str      =open_list[0].top_show()
                              visited.add(SCREAMING_SNAKE_CASE__		)
                              expand_state(
                                  SCREAMING_SNAKE_CASE__       ,  0       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  SCREAMING_SNAKE_CASE__       ,  )
                              close_list_anchor.append(SCREAMING_SNAKE_CASE__		)
      print("No path found to goal"		)
      print()
      for i in range(n - 1       ,  -1       ,  -1		):
            for j in range(SCREAMING_SNAKE_CASE__		):
                  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      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				if len(SCREAMING_SNAKE_CASE__	) <= 1 or n <= 1:
								return

				insert_next(SCREAMING_SNAKE_CASE__				, n - 1	)
				rec_insertion_sort(SCREAMING_SNAKE_CASE__				, n - 1	)







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				if index >= len(SCREAMING_SNAKE_CASE__	) or collection[index - 1] <= collection[index]:
								return

				# Swaps adjacent elements since they are not in ascending order
				_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			List[Any]							= (
				    collection[index],
				    collection[index - 1],
				)

				insert_next(SCREAMING_SNAKE_CASE__				, index + 1	)


if __name__ == "__main__":
				UpperCAmelCase_						:  List[str]				  =						input('Enter integers separated by spaces: ')
				UpperCAmelCase_						:  list[int]				  =						[int(num) for num in numbers.split()]
				rec_insertion_sort(number_list, len(number_list))
				print(number_list)




