





import heapq
import sys

import numpy as np

_UpperCAmelCase             =							tuple[int, int]






class        snake_case_    :






  def __init__(							self			:					List[Any]      )->List[Any]:






   '''simple docstring'''

   __lowerCAmelCase					:	Any      =       []
   __lowerCAmelCase					:	Tuple      =       set()






  def 				UpperCAmelCase__						(							self			:					Dict      )->int:






   '''simple docstring'''

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






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






   '''simple docstring'''

   return len(self.elements      ) == 0






  def 				UpperCAmelCase__						(							self			:					Optional[int]       ,  _snake_case			:					List[Any]       ,  _snake_case			:					int      )->Any:






   '''simple docstring'''

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






  def 				UpperCAmelCase__						(							self			:					List[str]       ,  _snake_case			:					int      )->Optional[Any]:






   '''simple docstring'''

   if item in self.set:
    self.set.remove(_snake_case      )
    __lowerCAmelCase					:	Tuple      =       []
    ((__lowerCAmelCase) ,					(__lowerCAmelCase))					:	Any      =       heapq.heappop(self.elements      )
    while x != item:
     temp.append((pro, x)      )
     ((__lowerCAmelCase) ,					(__lowerCAmelCase))					:	Union[str, Any]      =       heapq.heappop(self.elements      )
    for prito, yyy in temp:
     heapq.heappush(self.elements       ,  (prito, yyy)      )






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






   '''simple docstring'''

   return self.elements[0][1]






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






   '''simple docstring'''

   ((__lowerCAmelCase) ,					(__lowerCAmelCase))					:	List[str]      =       heapq.heappop(self.elements      )
   self.set.remove(_snake_case      )
   return (priority, item)






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:TPos   )      ->   List[str]:
 # euclidean distance
 __lowerCAmelCase					:	int      =       np.array(SCREAMING_SNAKE_CASE   )
 __lowerCAmelCase					:	Tuple      =       np.array(SCREAMING_SNAKE_CASE   )
 return np.linalg.norm(a - b   )






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:TPos   )      ->   str:
 # integer division by time variable
 return consistent_heuristic(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ) // t






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:TPos   )      ->   Optional[Any]:
 # manhattan distance
 return abs(p[0] - goal[0]   ) + abs(p[1] - goal[1]   )






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:int   ,   SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:dict[TPos, float]   )      ->   str:
 __lowerCAmelCase					:	str      =       g_function[start] + Wa * heuristics[i](SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )
 return ans






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:Tuple   ,   SCREAMING_SNAKE_CASE		:Tuple   ,   SCREAMING_SNAKE_CASE		:Any   )      ->   Tuple:
 __lowerCAmelCase					:	Optional[Any]      =       np.chararray((n, n)   )
 for i in range(SCREAMING_SNAKE_CASE   ):
  for j in range(SCREAMING_SNAKE_CASE   ):
   __lowerCAmelCase					:	List[Any]      =       """*"""

 for i in range(SCREAMING_SNAKE_CASE   ):
  for j in range(SCREAMING_SNAKE_CASE   ):
   if (j, (n - 1) - i) in blocks:
    __lowerCAmelCase					:	Dict      =       """#"""

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

 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:-"""   )
 __lowerCAmelCase					:	str      =       back_pointer[goal]
 while x != start:
  print(SCREAMING_SNAKE_CASE   ,   end=""" """   )
  __lowerCAmelCase					:	str      =       back_pointer[x]
 print(SCREAMING_SNAKE_CASE   )
 sys.exit()






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:TPos   )      ->   str:
 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 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:Any   ,   SCREAMING_SNAKE_CASE		:Optional[Any]   ,   SCREAMING_SNAKE_CASE		:Dict   ,   SCREAMING_SNAKE_CASE		:str   ,   SCREAMING_SNAKE_CASE		:str   ,   SCREAMING_SNAKE_CASE		:Tuple   ,   SCREAMING_SNAKE_CASE		:Union[str, Any]   ,   SCREAMING_SNAKE_CASE		:str   ,   )      ->   Union[str, Any]:
 for itera in range(SCREAMING_SNAKE_CASE   ):
  open_list[itera].remove_element(SCREAMING_SNAKE_CASE   )
 # print("s", s)
 # print("j", j)
 ((__lowerCAmelCase) ,					(__lowerCAmelCase))					:	str      =       s
 __lowerCAmelCase					:	Union[str, Any]      =       (x - 1, y)
 __lowerCAmelCase					:	Optional[Any]      =       (x + 1, y)
 __lowerCAmelCase					:	int      =       (x, y + 1)
 __lowerCAmelCase					:	Optional[int]      =       (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   )
    __lowerCAmelCase					:	Optional[Any]      =       -1
    __lowerCAmelCase					:	List[Any]      =       float("""inf"""   )

   if valid(SCREAMING_SNAKE_CASE   ) and g_function[neighbours] > g_function[s] + 1:
    __lowerCAmelCase					:	Union[str, Any]      =       g_function[s] + 1
    __lowerCAmelCase					:	int      =       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 	_SCREAMING_SNAKE_CASE		(      )      ->   Any:
 __lowerCAmelCase					:	str      =       []
 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


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

_UpperCAmelCase             =							[
    (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),
]
_UpperCAmelCase             =							make_common_ground()


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

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

_UpperCAmelCase             =							1






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:TPos   ,   SCREAMING_SNAKE_CASE		:int   )      ->   Dict:
 __lowerCAmelCase					:	List[Any]      =       {start: 0, goal: float("""inf"""   )}
 __lowerCAmelCase					:	Dict      =       {start: -1, goal: -1}
 __lowerCAmelCase					:	str      =       []
 __lowerCAmelCase					:	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   )   )

 __lowerCAmelCase					:	list[int]      =       []
 __lowerCAmelCase					:	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:
     __lowerCAmelCase ,					__lowerCAmelCase					:	Optional[Any]      =       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:
     __lowerCAmelCase					:	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)






import random






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:list   ,   SCREAMING_SNAKE_CASE		:Dict   )      ->   tuple:
 __lowerCAmelCase ,					__lowerCAmelCase ,					__lowerCAmelCase					:	List[str]      =       [], [], []
 for element in data:
  if element < pivot:
   less.append(SCREAMING_SNAKE_CASE   )
  elif element > pivot:
   greater.append(SCREAMING_SNAKE_CASE   )
  else:
   equal.append(SCREAMING_SNAKE_CASE   )
 return less, equal, greater







def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:list   ,   SCREAMING_SNAKE_CASE		:int   )      ->   Dict:
 # index = len(items) // 2 when trying to find the median
 #   (value of index when items is sorted)

 # invalid input
 if index >= len(SCREAMING_SNAKE_CASE   ) or index < 0:
  return None

 __lowerCAmelCase					:	Union[str, Any]      =       items[random.randint(0   ,   len(SCREAMING_SNAKE_CASE   ) - 1   )]
 __lowerCAmelCase					:	int      =       0
 __lowerCAmelCase ,					__lowerCAmelCase ,					__lowerCAmelCase					:	Tuple      =       _partition(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )
 __lowerCAmelCase					:	Optional[int]      =       len(SCREAMING_SNAKE_CASE   )
 __lowerCAmelCase					:	List[str]      =       len(SCREAMING_SNAKE_CASE   )

 # index is the pivot
 if m <= index < m + count:
  return pivot
 # must be in smaller
 elif m > index:
  return quick_select(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )
 # must be in larger
 else:
  return quick_select(SCREAMING_SNAKE_CASE   ,   index - (m + count)   )