'''simple docstring'''






import heapq
import sys

import numpy as np

SCREAMING_SNAKE_CASE_	   =			tuple[int, int]




class    a :



  """simple docstring"""







  def __init__(							self					):

    '''simple docstring'''







    __UpperCAmelCase:					Union[str, Any]		= []
    __UpperCAmelCase:					Tuple		= set()







  def    lowercase_  (							self					):

    '''simple docstring'''







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







  def    lowercase_  (							self					):

    '''simple docstring'''







    return len(self.elements					) == 0







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    if item not in self.set:
      heapq.heappush(self.elements   ,    (priority, item)					)
      self.set.add(snake_case_					)
    else:
      # update
      # print("update", item)
      __UpperCAmelCase:					List[str]		= []
      ((__UpperCAmelCase), (__UpperCAmelCase)):					Optional[Any]		= heapq.heappop(self.elements					)
      while x != item:
        temp.append((pri, x)					)
        ((__UpperCAmelCase), (__UpperCAmelCase)):					Tuple		= heapq.heappop(self.elements					)
      temp.append((priority, item)					)
      for pro, xxx in temp:
        heapq.heappush(self.elements   ,    (pro, xxx)					)







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    if item in self.set:
      self.set.remove(snake_case_					)
      __UpperCAmelCase:					Optional[int]		= []
      ((__UpperCAmelCase), (__UpperCAmelCase)):					Any		= heapq.heappop(self.elements					)
      while x != item:
        temp.append((pro, x)					)
        ((__UpperCAmelCase), (__UpperCAmelCase)):					List[Any]		= heapq.heappop(self.elements					)
      for prito, yyy in temp:
        heapq.heappush(self.elements   ,    (prito, yyy)					)







  def    lowercase_  (							self					):

    '''simple docstring'''







    return self.elements[0][1]







  def    lowercase_  (							self					):

    '''simple docstring'''







    ((__UpperCAmelCase), (__UpperCAmelCase)):					Union[str, Any]		= heapq.heappop(self.elements					)
    self.set.remove(snake_case_					)
    return (priority, item)






def  UpperCamelCase__					(					_lowercase    :				TPos   ,    _lowercase    :				TPos     )							->	Union[str, Any]:
  # euclidean distance
  __UpperCAmelCase:					Tuple		= np.array(_lowercase     )
  __UpperCAmelCase:					List[str]		= np.array(_lowercase     )
  return np.linalg.norm(a - b     )






def  UpperCamelCase__					(					_lowercase    :				TPos   ,    _lowercase    :				TPos     )							->	List[Any]:
  # integer division by time variable
  return consistent_heuristic(_lowercase   ,    _lowercase     ) // t






def  UpperCamelCase__					(					_lowercase    :				TPos   ,    _lowercase    :				TPos     )							->	Union[str, Any]:
  # manhattan distance
  return abs(p[0] - goal[0]     ) + abs(p[1] - goal[1]     )






def  UpperCamelCase__					(					_lowercase    :				TPos   ,    _lowercase    :				int   ,    _lowercase    :				TPos   ,    _lowercase    :				dict[TPos, float]     )							->	Dict:
  __UpperCAmelCase:					Any		= g_function[start] + Wa * heuristics[i](_lowercase   ,    _lowercase     )
  return ans






def  UpperCamelCase__					(					_lowercase    :				Any   ,    _lowercase    :				Any   ,    _lowercase    :				Optional[int]     )							->	Dict:
  __UpperCAmelCase:					Dict		= np.chararray((n, n)     )
  for i in range(_lowercase     ):
    for j in range(_lowercase     ):
      __UpperCAmelCase:					int		= """*"""

  for i in range(_lowercase     ):
    for j in range(_lowercase     ):
      if (j, (n - 1) - i) in blocks:
        __UpperCAmelCase:					int		= """#"""

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

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






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

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

      if valid(_lowercase     ) and g_function[neighbours] > g_function[s] + 1:
        __UpperCAmelCase:					List[str]		= g_function[s] + 1
        __UpperCAmelCase:					Optional[int]		= s
        if neighbours not in close_list_anchor:
          open_list[0].put(_lowercase   ,    key(_lowercase   ,    0   ,    _lowercase   ,    _lowercase     )     )
          if neighbours not in close_list_inad:
            for var in range(1   ,    _lowercase     ):
              if key(_lowercase   ,    _lowercase   ,    _lowercase   ,    _lowercase     ) <= Wa * key(
                  _lowercase   ,    0   ,    _lowercase   ,    _lowercase     ):
                open_list[j].put(
                    _lowercase   ,    key(_lowercase   ,    _lowercase   ,    _lowercase   ,    _lowercase     )     )






def  UpperCamelCase__					(					)							->	Any:
  __UpperCAmelCase:					Optional[int]		= []
  for x in range(1   ,    5     ):
    for y in range(1   ,    6     ):
      some_list.append((x, y)     )

  for x in range(1_5   ,    2_0     ):
    some_list.append((x, 1_7)     )

  for x in range(1_0   ,    1_9     ):
    for y in range(1   ,    1_5     ):
      some_list.append((x, y)     )

    # L block
  for x in range(1   ,    4     ):
    for y in range(1_2   ,    1_9     ):
      some_list.append((x, y)     )
  for x in range(3   ,    1_3     ):
    for y in range(1_6   ,    1_9     ):
      some_list.append((x, y)     )
  return some_list


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

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


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

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

SCREAMING_SNAKE_CASE_	   =			1






def  UpperCamelCase__					(					_lowercase    :				TPos   ,    _lowercase    :				TPos   ,    _lowercase    :				int     )							->	int:
  __UpperCAmelCase:					Any		= {start: 0, goal: float("""inf"""     )}
  __UpperCAmelCase:					Tuple		= {start: -1, goal: -1}
  __UpperCAmelCase:					Any		= []
  __UpperCAmelCase:					Tuple		= set()

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

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

import math
import random
from collections.abc import Collection
from typing import overload




class    a :



  """simple docstring"""







  def __init__(							self   ,    snake_case_ = None					):

    '''simple docstring'''







    if components is None:
      __UpperCAmelCase:					List[Any]		= []
    __UpperCAmelCase:					Tuple		= list(snake_case_					)







  def __len__(							self					):

    '''simple docstring'''







    return len(self.__components					)







  def __str__(							self					):

    '''simple docstring'''







    return "(" + ",".join(map(snake_case_   ,    self.__components					)					) + ")"







  def __add__(							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					int		= len(self					)
    if size == len(snake_case_					):
      __UpperCAmelCase:					str		= [self.__components[i] + other.component(snake_case_					) for i in range(snake_case_					)]
      return Vector(snake_case_					)
    else:
      raise Exception("""must have the same size"""					)







  def __sub__(							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Dict		= len(self					)
    if size == len(snake_case_					):
      __UpperCAmelCase:					Dict		= [self.__components[i] - other.component(snake_case_					) for i in range(snake_case_					)]
      return Vector(snake_case_					)
    else:  # error case
      raise Exception("""must have the same size"""					)







  @overload
  def __mul__(							self   ,    snake_case_					):

    '''simple docstring'''







    ...







  @overload
  def __mul__(							self   ,    snake_case_					):

    '''simple docstring'''







    ...







  def __mul__(							self   ,    snake_case_					):

    '''simple docstring'''







    if isinstance(snake_case_   ,    (float, int)					):
      __UpperCAmelCase:					str		= [c * other for c in self.__components]
      return Vector(snake_case_					)
    elif isinstance(snake_case_   ,    snake_case_					) and len(self					) == len(snake_case_					):
      __UpperCAmelCase:					Dict		= len(self					)
      __UpperCAmelCase:					List[str]		= [self.__components[i] * other.component(snake_case_					) for i in range(snake_case_					)]
      return sum(snake_case_					)
    else:  # error case
      raise Exception("""invalid operand!"""					)







  def    lowercase_  (							self					):

    '''simple docstring'''







    return Vector(self.__components					)







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    if isinstance(snake_case_   ,    snake_case_					) and -len(self.__components					) <= i < len(self.__components					):
      return self.__components[i]
    else:
      raise Exception("""index out of range"""					)







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    assert -len(self.__components					) <= pos < len(self.__components					)
    __UpperCAmelCase:					List[str]		= value







  def    lowercase_  (							self					):

    '''simple docstring'''







    if len(self.__components					) == 0:
      raise Exception("""Vector is empty"""					)
    __UpperCAmelCase:					Optional[Any]		= [c**2 for c in self.__components]
    return math.sqrt(sum(snake_case_					)					)







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_ = False					):

    '''simple docstring'''







    __UpperCAmelCase:					List[Any]		= self * other
    __UpperCAmelCase:					Any		= self.euclidean_length() * other.euclidean_length()
    if deg:
      return math.degrees(math.acos(num / den					)					)
    else:
      return math.acos(num / den					)






def  UpperCamelCase__					(					_lowercase    :				int     )							->	Vector:
  assert isinstance(_lowercase   ,    _lowercase     )
  return Vector([0] * dimension     )






def  UpperCamelCase__					(					_lowercase    :				int   ,    _lowercase    :				int     )							->	Vector:
  assert isinstance(_lowercase   ,    _lowercase     ) and (isinstance(_lowercase   ,    _lowercase     ))
  __UpperCAmelCase:					int		= [0] * dimension
  __UpperCAmelCase:					int		= 1
  return Vector(_lowercase     )






def  UpperCamelCase__					(					_lowercase    :				float   ,    _lowercase    :				Vector   ,    _lowercase    :				Vector     )							->	Vector:
  assert (
      isinstance(_lowercase   ,    _lowercase     )
      and isinstance(_lowercase   ,    _lowercase     )
      and (isinstance(_lowercase   ,    (int, float)     ))
  )
  return x * scalar + y






def  UpperCamelCase__					(					_lowercase    :				int   ,    _lowercase    :				int   ,    _lowercase    :				int     )							->	Vector:
  random.seed(_lowercase     )
  __UpperCAmelCase:					str		= [random.randint(_lowercase   ,    _lowercase     ) for _ in range(_lowercase     )]
  return Vector(_lowercase     )




class    a :



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					List[str]		= matrix
    __UpperCAmelCase:					Dict		= w
    __UpperCAmelCase:					Tuple		= h







  def __str__(							self					):

    '''simple docstring'''







    __UpperCAmelCase:					Optional[int]		= """"""
    for i in range(self.__height					):
      ans += "|"
      for j in range(self.__width					):
        if j < self.__width - 1:
          ans += str(self.__matrix[i][j]					) + ","
        else:
          ans += str(self.__matrix[i][j]					) + "|\n"
    return ans







  def __add__(							self   ,    snake_case_					):

    '''simple docstring'''







    if self.__width == other.width() and self.__height == other.height():
      __UpperCAmelCase:					List[str]		= []
      for i in range(self.__height					):
        __UpperCAmelCase:					List[Any]		= [
            self.__matrix[i][j] + other.component(snake_case_   ,    snake_case_					)
            for j in range(self.__width					)
        ]
        matrix.append(snake_case_					)
      return Matrix(snake_case_   ,    self.__width   ,    self.__height					)
    else:
      raise Exception("""matrix must have the same dimension!"""					)







  def __sub__(							self   ,    snake_case_					):

    '''simple docstring'''







    if self.__width == other.width() and self.__height == other.height():
      __UpperCAmelCase:					int		= []
      for i in range(self.__height					):
        __UpperCAmelCase:					Any		= [
            self.__matrix[i][j] - other.component(snake_case_   ,    snake_case_					)
            for j in range(self.__width					)
        ]
        matrix.append(snake_case_					)
      return Matrix(snake_case_   ,    self.__width   ,    self.__height					)
    else:
      raise Exception("""matrices must have the same dimension!"""					)







  @overload
  def __mul__(							self   ,    snake_case_					):

    '''simple docstring'''







    ...







  @overload
  def __mul__(							self   ,    snake_case_					):

    '''simple docstring'''







    ...







  def __mul__(							self   ,    snake_case_					):

    '''simple docstring'''







    if isinstance(snake_case_   ,    snake_case_					):  # matrix-vector
      if len(snake_case_					) == self.__width:
        __UpperCAmelCase:					Optional[Any]		= zero_vector(self.__height					)
        for i in range(self.__height					):
          __UpperCAmelCase:					Dict		= [
              self.__matrix[i][j] * other.component(snake_case_					)
              for j in range(self.__width					)
          ]
          ans.change_component(snake_case_   ,    sum(snake_case_					)					)
        return ans
      else:
        raise Exception(
            """vector must have the same size as the """
            """number of columns of the matrix!"""					)
    elif isinstance(snake_case_   ,    (int, float)					):  # matrix-scalar
      __UpperCAmelCase:					Dict		= [
          [self.__matrix[i][j] * other for j in range(self.__width					)]
          for i in range(self.__height					)
      ]
      return Matrix(snake_case_   ,    self.__width   ,    self.__height					)
    return None







  def    lowercase_  (							self					):

    '''simple docstring'''







    return self.__height







  def    lowercase_  (							self					):

    '''simple docstring'''







    return self.__width







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    if 0 <= x < self.__height and 0 <= y < self.__width:
      return self.__matrix[x][y]
    else:
      raise Exception("""change_component: indices out of bounds"""					)







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    if 0 <= x < self.__height and 0 <= y < self.__width:
      __UpperCAmelCase:					int		= value
    else:
      raise Exception("""change_component: indices out of bounds"""					)







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    if self.__height != self.__width:
      raise Exception("""Matrix is not square"""					)
    __UpperCAmelCase:					int		= self.__matrix[:x] + self.__matrix[x + 1 :]
    for i in range(len(snake_case_					)					):
      __UpperCAmelCase:					Optional[Any]		= minor[i][:y] + minor[i][y + 1 :]
    return Matrix(snake_case_   ,    self.__width - 1   ,    self.__height - 1					).determinant()







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    if self.__height != self.__width:
      raise Exception("""Matrix is not square"""					)
    if 0 <= x < self.__height and 0 <= y < self.__width:
      return (-1) ** (x + y) * self.minor(snake_case_   ,    snake_case_					)
    else:
      raise Exception("""Indices out of bounds"""					)







  def    lowercase_  (							self					):

    '''simple docstring'''







    if self.__height != self.__width:
      raise Exception("""Matrix is not square"""					)
    if self.__height < 1:
      raise Exception("""Matrix has no element"""					)
    elif self.__height == 1:
      return self.__matrix[0][0]
    elif self.__height == 2:
      return (
          self.__matrix[0][0] * self.__matrix[1][1]
          - self.__matrix[0][1] * self.__matrix[1][0]
      )
    else:
      __UpperCAmelCase:					Any		= [
          self.__matrix[0][y] * self.cofactor(0   ,    snake_case_					) for y in range(self.__width					)
      ]
      return sum(snake_case_					)






def  UpperCamelCase__					(					_lowercase    :				int     )							->	Matrix:
  __UpperCAmelCase:					list[list[float]]		= [[0] * n for _ in range(_lowercase     )]
  return Matrix(_lowercase   ,    _lowercase   ,    _lowercase     )







def  UpperCamelCase__					(					_lowercase    :				int   ,    _lowercase    :				int   ,    _lowercase    :				int   ,    _lowercase    :				int     )							->	Matrix:
  random.seed(_lowercase     )
  __UpperCAmelCase:					list[list[float]]		= [
      [random.randint(_lowercase   ,    _lowercase     ) for _ in range(_lowercase     )] for _ in range(_lowercase     )
  ]
  return Matrix(_lowercase   ,    _lowercase   ,    _lowercase     )