





def    __lowerCamelCase					(							__a   :int    ,     __a   :bool = False    )		->				bool:






		"""simple docstring"""

		if n == 2:
				return True
		if not n % 2 or n < 2:
				return False
		if n > 5 and n % 1_0 not in (1, 3, 7, 9):  # can quickly check last digit
				return False
		if n > 3_3_1_7_0_4_4_0_6_4_6_7_9_8_8_7_3_8_5_9_6_1_9_8_1 and not allow_probable:
				raise ValueError(
				    """Warning: upper bound of deterministic test is exceeded. """
				    """Pass allow_probable=True to allow probabilistic test. """
				    """A return value of True indicates a probable prime."""    )
		# array bounds provided by analysis
		A__        =   [
		    2_0_4_7,
		    1_3_7_3_6_5_3,
		    2_5_3_2_6_0_0_1,
		    3_2_1_5_0_3_1_7_5_1,
		    2_1_5_2_3_0_2_8_9_8_7_4_7,
		    3_4_7_4_7_4_9_6_6_0_3_8_3,
		    3_4_1_5_5_0_0_7_1_7_2_8_3_2_1,
		    1,
		    3_8_2_5_1_2_3_0_5_6_5_4_6_4_1_3_0_5_1,
		    1,
		    1,
		    3_1_8_6_6_5_8_5_7_8_3_4_0_3_1_1_5_1_1_6_7_4_6_1,
		    3_3_1_7_0_4_4_0_6_4_6_7_9_8_8_7_3_8_5_9_6_1_9_8_1,
		]

		A__        =   [2, 3, 5, 7, 1_1, 1_3, 1_7, 1_9, 2_3, 2_9, 3_1, 3_7, 4_1]
		for idx, _p in enumerate(__a    ,     1    ):
				if n < _p:
						# then we have our last prime to check
						A__        =   primes[:idx]
						break
		A__      ,			A__        =   n - 1, 0
		# break up n -1 into a power of 2 (s) and
		# remaining odd component
		# essentially, solve for d * 2 ** s == n - 1
		while d % 2 == 0:
				d //= 2
				s += 1
		for prime in plist:
				A__        =   False
				for r in range(__a    ):
						A__        =   pow(__a    ,     d * 2**r    ,     __a    )
						# see article for analysis explanation for m
						if (r == 0 and m == 1) or ((m + 1) % n == 0):
								A__        =   True
								# this loop will not determine compositeness
								break
				if pr:
						continue
				# if pr is False, then the above loop never evaluated to true,
				# and the n MUST be composite
				return False
		return True







def    __lowerCamelCase					(							)		->				None:






		"""simple docstring"""

		assert not miller_rabin(5_6_1    )
		assert miller_rabin(5_6_3    )
		# 2047

		assert not miller_rabin(8_3_8_2_0_1    )
		assert miller_rabin(8_3_8_2_0_7    )
		# 1_373_653

		assert not miller_rabin(1_7_3_1_6_0_0_1    )
		assert miller_rabin(1_7_3_1_6_0_1_7    )
		# 25_326_001

		assert not miller_rabin(3_0_7_8_3_8_6_6_4_1    )
		assert miller_rabin(3_0_7_8_3_8_6_6_5_3    )
		# 3_215_031_751

		assert not miller_rabin(1_7_1_3_0_4_5_5_7_4_8_0_1    )
		assert miller_rabin(1_7_1_3_0_4_5_5_7_4_8_1_9    )
		# 2_152_302_898_747

		assert not miller_rabin(2_7_7_9_7_9_9_7_2_8_3_0_7    )
		assert miller_rabin(2_7_7_9_7_9_9_7_2_8_3_2_7    )
		# 3_474_749_660_383

		assert not miller_rabin(1_1_3_8_5_0_0_2_3_9_0_9_4_4_1    )
		assert miller_rabin(1_1_3_8_5_0_0_2_3_9_0_9_5_2_7    )
		# 341_550_071_728_321

		assert not miller_rabin(1_2_7_5_0_4_1_0_1_8_8_4_8_8_0_4_3_5_1    )
		assert miller_rabin(1_2_7_5_0_4_1_0_1_8_8_4_8_8_0_4_3_9_1    )
		# 3_825_123_056_546_413_051

		assert not miller_rabin(7_9_6_6_6_4_6_4_4_5_8_5_0_7_7_8_7_7_9_1_8_6_7    )
		assert miller_rabin(7_9_6_6_6_4_6_4_4_5_8_5_0_7_7_8_7_7_9_1_9_5_1    )
		# 318_665_857_834_031_151_167_461

		assert not miller_rabin(5_5_2_8_4_0_6_7_7_4_4_6_6_4_7_8_9_7_6_6_0_3_3_3    )
		assert miller_rabin(5_5_2_8_4_0_6_7_7_4_4_6_6_4_7_8_9_7_6_6_0_3_5_9    )
		# 3_317_044_064_679_887_385_961_981
		# upper limit for probabilistic test


if __name__ == "__main__":
					test_miller_rabin()










from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
A    :					str =      0

A    :					Any =      [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

A    :					Dict =      [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

A    :					Union[str, Any] =      tuple[int, int]


class   A			:
			'''simple docstring'''




			def __init__(			self   :    int							,	__lowerCAmelCase   :    int							,	__lowerCAmelCase   :    int							,	__lowerCAmelCase   :    int							,	__lowerCAmelCase   :    int							,	__lowerCAmelCase   :    int							,	__lowerCAmelCase   :    Node | None							,	)	->	None:







					"""simple docstring"""






					A__        =   pos_x
					A__        =   pos_y
					A__        =   (pos_y, pos_x)
					A__        =   goal_x
					A__        =   goal_y
					A__        =   g_cost
					A__        =   parent
					A__        =   self.calculate_heuristic()
					A__        =   self.g_cost + self.h_cost






			def    a_       (			self   :    Dict   )	->	float:







					"""simple docstring"""






					A__        =   self.pos_x - self.goal_x
					A__        =   self.pos_y - self.goal_y
					if HEURISTIC == 1:
							return abs(__lowerCAmelCase   ) + abs(__lowerCAmelCase   )
					else:
							return sqrt(dy**2 + dx**2   )







			def __lt__(			self   :    int							,	__lowerCAmelCase   :    Node   )	->	bool:







					"""simple docstring"""






					return self.f_cost < other.f_cost


class   A			:
			'''simple docstring'''




			def __init__(			self   :    Union[str, Any]							,	__lowerCAmelCase   :    TPosition							,	__lowerCAmelCase   :    TPosition   )	->	Tuple:







					"""simple docstring"""






					A__        =   Node(start[1]							,	start[0]							,	goal[1]							,	goal[0]							,	0							,	__lowerCAmelCase   )
					A__        =   Node(goal[1]							,	goal[0]							,	goal[1]							,	goal[0]							,	9_99_99							,	__lowerCAmelCase   )

					A__        =   [self.start]
					A__        =   []

					A__        =   False






			def    a_       (			self   :    List[str]   )	->	list[TPosition]:







					"""simple docstring"""






					while self.open_nodes:
							# Open Nodes are sorted using __lt__
							self.open_nodes.sort()
							A__        =   self.open_nodes.pop(0   )

							if current_node.pos == self.target.pos:
									return self.retrace_path(__lowerCAmelCase   )

							self.closed_nodes.append(__lowerCAmelCase   )
							A__        =   self.get_successors(__lowerCAmelCase   )

							for child_node in successors:
									if child_node in self.closed_nodes:
											continue

									if child_node not in self.open_nodes:
											self.open_nodes.append(__lowerCAmelCase   )
									else:
											# retrieve the best current path
											A__        =   self.open_nodes.pop(self.open_nodes.index(__lowerCAmelCase   )   )

											if child_node.g_cost < better_node.g_cost:
													self.open_nodes.append(__lowerCAmelCase   )
											else:
													self.open_nodes.append(__lowerCAmelCase   )

					return [self.start.pos]






			def    a_       (			self   :    Optional[Any]							,	__lowerCAmelCase   :    Node   )	->	list[Node]:







					"""simple docstring"""






					A__        =   []
					for action in delta:
							A__        =   parent.pos_x + action[1]
							A__        =   parent.pos_y + action[0]
							if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(__lowerCAmelCase   ) - 1):
									continue

							if grid[pos_y][pos_x] != 0:
									continue

							successors.append(
							    Node(
							        __lowerCAmelCase							,	__lowerCAmelCase							,	self.target.pos_y							,	self.target.pos_x							,	parent.g_cost + 1							,	__lowerCAmelCase							,	)   )
					return successors







			def    a_       (			self   :    List[Any]							,	__lowerCAmelCase   :    Node | None   )	->	list[TPosition]:







					"""simple docstring"""






					A__        =   node
					A__        =   []
					while current_node is not None:
							path.append((current_node.pos_y, current_node.pos_x)   )
							A__        =   current_node.parent
					path.reverse()
					return path


class   A			:
			'''simple docstring'''




			def __init__(			self   :    Optional[Any]							,	__lowerCAmelCase   :    TPosition							,	__lowerCAmelCase   :    TPosition   )	->	None:







					"""simple docstring"""






					A__        =   AStar(__lowerCAmelCase							,	__lowerCAmelCase   )
					A__        =   AStar(__lowerCAmelCase							,	__lowerCAmelCase   )
					A__        =   False






			def    a_       (			self   :    int   )	->	list[TPosition]:







					"""simple docstring"""






					while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
							self.fwd_astar.open_nodes.sort()
							self.bwd_astar.open_nodes.sort()
							A__        =   self.fwd_astar.open_nodes.pop(0   )
							A__        =   self.bwd_astar.open_nodes.pop(0   )

							if current_bwd_node.pos == current_fwd_node.pos:
									return self.retrace_bidirectional_path(
									    __lowerCAmelCase							,	__lowerCAmelCase   )

							self.fwd_astar.closed_nodes.append(__lowerCAmelCase   )
							self.bwd_astar.closed_nodes.append(__lowerCAmelCase   )

							A__        =   current_bwd_node
							A__        =   current_fwd_node

							A__        =   {
							    self.fwd_astar: self.fwd_astar.get_successors(__lowerCAmelCase   ),
							    self.bwd_astar: self.bwd_astar.get_successors(__lowerCAmelCase   ),
							}

							for astar in [self.fwd_astar, self.bwd_astar]:
									for child_node in successors[astar]:
											if child_node in astar.closed_nodes:
													continue

											if child_node not in astar.open_nodes:
													astar.open_nodes.append(__lowerCAmelCase   )
											else:
													# retrieve the best current path
													A__        =   astar.open_nodes.pop(
													    astar.open_nodes.index(__lowerCAmelCase   )   )

													if child_node.g_cost < better_node.g_cost:
															astar.open_nodes.append(__lowerCAmelCase   )
													else:
															astar.open_nodes.append(__lowerCAmelCase   )

					return [self.fwd_astar.start.pos]







			def    a_       (			self   :    List[str]							,	__lowerCAmelCase   :    Node							,	__lowerCAmelCase   :    Node   )	->	list[TPosition]:







					"""simple docstring"""






					A__        =   self.fwd_astar.retrace_path(__lowerCAmelCase   )
					A__        =   self.bwd_astar.retrace_path(__lowerCAmelCase   )
					bwd_path.pop()
					bwd_path.reverse()
					A__        =   fwd_path + bwd_path
					return path


if __name__ == "__main__":
					# all coordinates are given in format [y,x]
					A    :					Optional[int] =      (0, 0)
					A    :					int =      (len(grid) - 1, len(grid[0]) - 1)
					for elem in grid:
										print(elem)

					A    :					Dict =      time.time()
					A    :					Optional[Any] =      AStar(init, goal)
					A    :					Optional[int] =      a_star.search()
					A    :					Optional[int] =      time.time() - start_time
					print(F'''AStar execution time = {end_time:f} seconds''')

					A    :					Dict =      time.time()
					A    :					Tuple =      BidirectionalAStar(init, goal)
					A    :					List[Any] =      time.time() - bd_start_time
					print(F'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')



