





import heapq
import sys

import numpy as np

lowerCAmelCase_        =							tuple[int, int]



class    __lowerCAmelCase			:






			def __init__(self       )	->  int:


							'''simple docstring'''



							snake_case_		:       int           =    []
							snake_case_		:       Dict           =    set()






			def      lowerCamelCase    (self       )	->  str:


							'''simple docstring'''



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






			def      lowerCamelCase    (self       )	->  str:


							'''simple docstring'''



							return len(self.elements       ) == 0






			def      lowerCamelCase    (self   ,				__magic_name__   ,				__magic_name__       )	->  List[Any]:


							'''simple docstring'''



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






			def      lowerCamelCase    (self   ,				__magic_name__       )	->  Tuple:


							'''simple docstring'''



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






			def      lowerCamelCase    (self       )	->  Tuple:


							'''simple docstring'''



							return self.elements[0][1]






			def      lowerCamelCase    (self       )	->  Optional[int]:


							'''simple docstring'''



							((snake_case_)     ,				(snake_case_))		:       Any           =    heapq.heappop(self.elements       )
							self.set.remove(__magic_name__       )
							return (priority, item)






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					)						->		List[Any]:






				"""simple docstring"""


				snake_case_		:       Union[str, Any]           =    np.array(_UpperCamelCase					)
				snake_case_		:       int           =    np.array(_UpperCamelCase					)
				return np.linalg.norm(a - b					)






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					)						->		Dict:






				"""simple docstring"""


				return consistent_heuristic(_UpperCamelCase					,							_UpperCamelCase					) // t






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					)						->		List[Any]:






				"""simple docstring"""


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






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					)						->		int:






				"""simple docstring"""


				snake_case_		:       Optional[int]           =    g_function[start] + Wa * heuristics[i](_UpperCamelCase					,							_UpperCamelCase					)
				return ans






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					)						->		Any:






				"""simple docstring"""


				snake_case_		:       List[Any]           =    np.chararray((n, n)					)
				for i in range(_UpperCamelCase					):
								for j in range(_UpperCamelCase					):
												snake_case_		:       Any           =    '''*'''

				for i in range(_UpperCamelCase					):
								for j in range(_UpperCamelCase					):
												if (j, (n - 1) - i) in blocks:
																snake_case_		:       Dict           =    '''#'''

				snake_case_		:       List[str]           =    '''-'''
				snake_case_		:       Dict           =    back_pointer[goal]
				while x != start:
								((snake_case_)     ,				(snake_case_))		:       Dict           =    x
								# print(x)
								snake_case_		:       Dict           =    '''-'''
								snake_case_		:       str           =    back_pointer[x]
				snake_case_		:       Union[str, Any]           =    '''-'''

				for i in range(_UpperCamelCase					):
								for j in range(_UpperCamelCase					):
												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:-'''					)
				snake_case_		:       Optional[int]           =    back_pointer[goal]
				while x != start:
								print(_UpperCamelCase					,							end=''' '''					)
								snake_case_		:       Tuple           =    back_pointer[x]
				print(_UpperCamelCase					)
				sys.exit()






def 	lowerCamelCase_		(							_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 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					,							)						->		Any:






				"""simple docstring"""


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

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

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






def 	lowerCamelCase_		(							)						->		Dict:






				"""simple docstring"""


				snake_case_		:       List[Any]           =    []
				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),
    (1_0, 1),
    (1_1, 1),
    (1_2, 1),
    (1_3, 1),
    (1_4, 1),
    (1_5, 1),
    (1_6, 1),
    (1_7, 1),
    (1_8, 1),
    (1_9, 1),
]
lowerCAmelCase_        =							make_common_ground()


lowerCAmelCase_        =							blocks_blk
# hyper parameters
lowerCAmelCase_        =							1
lowerCAmelCase_        =							1
lowerCAmelCase_        =							2_0
lowerCAmelCase_        =							3  # one consistent and two other inconsistent

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

lowerCAmelCase_        =							1






def 	lowerCamelCase_		(							_UpperCamelCase					,							_UpperCamelCase					,							_UpperCamelCase					)						->		Optional[int]:






				"""simple docstring"""


				snake_case_		:       Optional[Any]           =    {start: 0, goal: float('''inf'''					)}
				snake_case_		:       int           =    {start: -1, goal: -1}
				snake_case_		:       Any           =    []
				snake_case_		:       Tuple           =    set()

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

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






def 		lowerCamelCase__       (						):







	'''simple docstring'''





	for n in range(1	,      1000000				):
		yield n * (n + 1) // 2


def 		lowerCamelCase__       (						_A				):







	'''simple docstring'''





	snake_case_						       =	1
	snake_case_						       =	2
	while i * i <= n:
		snake_case_						       =	0
		while n % i == 0:
			n //= i
			multiplicity += 1
		divisors_count *= multiplicity + 1
		i += 1
	if n > 1:
		divisors_count *= 2
	return divisors_count


def 		lowerCamelCase__       (						):







	'''simple docstring'''





	return next(i for i in triangle_number_generator() if count_divisors(_A				) > 500				)


if __name__ == "__main__":
		print(solution())
