import heapq
import sys

import numpy as np

A__           =							tuple[int, int]
class   _lowerCAmelCase		:







							def __init__(				self     :    str		):
										lowerCamelCase						:int						  =     []
										lowerCamelCase						:List[str]						  =     set()







							def 				snake_case  (				self     :    List[str]		):
										if not self.empty():
													return self.elements[0][0]
										else:
													return float('''inf'''		)







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







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







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







							def 				snake_case  (				self     :    str		):
										return self.elements[0][1]







							def 				snake_case  (				self     :    List[str]		):
										((lowerCamelCase)  ,    (lowerCamelCase))						:str						  =     heapq.heappop(self.elements		)
										self.set.remove(__snake_case		)
										return (priority, item)





def  _lowerCamelCase					(   a_				: TPos						,			a_				: TPos):
			# euclidean distance
			lowerCamelCase						:Optional[int]						  =     np.array(a_)
			lowerCamelCase						:Union[str, Any]						  =     np.array(a_)
			return np.linalg.norm(a - b)





def  _lowerCamelCase					(   a_				: TPos						,			a_				: TPos):
			# integer division by time variable
			return consistent_heuristic(a_						,			a_) // t





def  _lowerCamelCase					(   a_				: TPos						,			a_				: TPos):
			# manhattan distance
			return abs(p[0] - goal[0]) + abs(p[1] - goal[1])





def  _lowerCamelCase					(   a_				: TPos						,			a_				: int						,			a_				: TPos						,			a_				: dict[TPos, float]):
			lowerCamelCase						:Optional[int]						  =     g_function[start] + Wa * heuristics[i](a_						,			a_)
			return ans





def  _lowerCamelCase					(   a_				: Optional[Any]						,			a_				: Tuple						,			a_				: str):
			lowerCamelCase						:List[str]						  =     np.chararray((n, n))
			for i in range(a_):
						for j in range(a_):
									lowerCamelCase						:Dict						  =     '''*'''

			for i in range(a_):
						for j in range(a_):
									if (j, (n - 1) - i) in blocks:
												lowerCamelCase						:str						  =     '''#'''

			lowerCamelCase						:Tuple						  =     '''-'''
			lowerCamelCase						:Optional[int]						  =     back_pointer[goal]
			while x != start:
						((lowerCamelCase)  ,    (lowerCamelCase))						:List[str]						  =     x
						# print(x)
						lowerCamelCase						:int						  =     '''-'''
						lowerCamelCase						:Dict						  =     back_pointer[x]
			lowerCamelCase						:Optional[Any]						  =     '''-'''

			for i in range(a_):
						for j in range(a_):
									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(a_						,			end=''' ''')
						lowerCamelCase						:List[str]						  =     back_pointer[x]
			print(a_)
			sys.exit()





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

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

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





def  _lowerCamelCase					(   ):
			lowerCamelCase						: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__           =							{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

A__           =							[
    (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__           =							make_common_ground()


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

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

A__           =							1





def  _lowerCamelCase					(   a_				: TPos						,			a_				: TPos						,			a_				: int):
			lowerCamelCase						:Dict						  =     {start: 0, goal: float('''inf''')}
			lowerCamelCase						:Optional[Any]						  =     {start: -1, goal: -1}
			lowerCamelCase						:Optional[Any]						  =     []
			lowerCamelCase						:Any						  =     set()

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

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





def  _lowerCamelCase					(   a_				: Tuple):
			lowerCamelCase						:int						  =     []
			lowerCamelCase						:List[str]						  =     lambda a_						,			a_: int(x / y)  # noqa: E731 integer division operation
			lowerCamelCase						:Optional[int]						  =     {
			    '''^''': op.pow,
			    '''*''': op.mul,
			    '''/''': div,
			    '''+''': op.add,
			    '''-''': op.sub,
			}  # operators & their respective operation

			# print table header
			print('''Symbol'''.center(8)						,			'''Action'''.center(12)						,			'''Stack'''						,			sep=''' | ''')
			print('''-''' * (30 + len(a_)))

			for x in post_fix:
						if x.isdigit():  # if x in digit
									stack.append(a_)  # append x to stack
									# output in tabular format
									print(x.rjust(8)						,			('''push(''' + x + ''')''').ljust(12)						,			''','''.join(a_)						,			sep=''' | ''')
						else:
									lowerCamelCase						:Optional[Any]						  =     stack.pop()  # pop stack
									# output in tabular format
									print(''''''.rjust(8)						,			('''pop(''' + b + ''')''').ljust(12)						,			''','''.join(a_)						,			sep=''' | ''')

									lowerCamelCase						:str						  =     stack.pop()  # pop stack
									# output in tabular format
									print(''''''.rjust(8)						,			('''pop(''' + a + ''')''').ljust(12)						,			''','''.join(a_)						,			sep=''' | ''')

									stack.append(
									    str(opr[x](int(a_)						,			int(a_))))  # evaluate the 2 values popped from stack & push result to stack
									# output in tabular format
									print(
									    x.rjust(8)						,			('''push(''' + a + x + b + ''')''').ljust(12)						,			''','''.join(a_)						,			sep=''' | '''						,			)

			return int(stack[0])


if __name__ == "__main__":
			A__           =							input("""\n\nEnter a Postfix Equation (space separated) = """).split(""" """)
			print("""\n\tResult = """, solve(Postfix))



