





from __future__ import annotations

import time

UpperCamelCase__											= list[tuple[int, int]]

UpperCamelCase__											= [
    [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],
]

UpperCamelCase__											= [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class        __SCREAMING_SNAKE_CASE					:






							def __init__(						self  , __lowerCAmelCase  , __lowerCAmelCase  , __lowerCAmelCase  , __lowerCAmelCase  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			pos_x
														UpperCamelCase__				     =			pos_y
														UpperCamelCase__				     =			(pos_y, pos_x)
														UpperCamelCase__				     =			goal_x
														UpperCamelCase__				     =			goal_y
														UpperCamelCase__				     =			parent






class        __SCREAMING_SNAKE_CASE					:






							def __init__(						self  , __lowerCAmelCase  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			Node(start[1]  , start[0]  , goal[1]  , goal[0]  , __lowerCAmelCase  )
														UpperCamelCase__				     =			Node(goal[1]  , goal[0]  , goal[1]  , goal[0]  , __lowerCAmelCase  )

														UpperCamelCase__				     =			[self.start]
														UpperCamelCase__				     =			False






							def 				_lowerCamelCase		(						self  ):
														while self.node_queue:
																					UpperCamelCase__				     =			self.node_queue.pop(0  )

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

																					UpperCamelCase__				     =			self.get_successors(__lowerCAmelCase  )

																					for node in successors:
																												self.node_queue.append(__lowerCAmelCase  )

														if not self.reached:
																					return [self.start.pos]
														return None






							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			[]
														for action in delta:
																					UpperCamelCase__				     =			parent.pos_x + action[1]
																					UpperCamelCase__				     =			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  , __lowerCAmelCase  )  )
														return successors







							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			node
														UpperCamelCase__				     =			[]
														while current_node is not None:
																					path.append((current_node.pos_y, current_node.pos_x)  )
																					UpperCamelCase__				     =			current_node.parent
														path.reverse()
														return path






class        __SCREAMING_SNAKE_CASE					:






							def __init__(						self  , __lowerCAmelCase  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			BreadthFirstSearch(__lowerCAmelCase  , __lowerCAmelCase  )
														UpperCamelCase__				     =			BreadthFirstSearch(__lowerCAmelCase  , __lowerCAmelCase  )
														UpperCamelCase__				     =			False






							def 				_lowerCamelCase		(						self  ):
														while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
																					UpperCamelCase__				     =			self.fwd_bfs.node_queue.pop(0  )
																					UpperCamelCase__				     =			self.bwd_bfs.node_queue.pop(0  )

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

																					UpperCamelCase__				     =			current_bwd_node
																					UpperCamelCase__				     =			current_fwd_node

																					UpperCamelCase__				     =			{
																					    self.fwd_bfs: self.fwd_bfs.get_successors(__lowerCAmelCase  ),
																					    self.bwd_bfs: self.bwd_bfs.get_successors(__lowerCAmelCase  ),
																					}

																					for bfs in [self.fwd_bfs, self.bwd_bfs]:
																												for node in successors[bfs]:
																																			bfs.node_queue.append(__lowerCAmelCase  )

														if not self.reached:
																					return [self.fwd_bfs.start.pos]
														return None







							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			self.fwd_bfs.retrace_path(__lowerCAmelCase  )
														UpperCamelCase__				     =			self.bwd_bfs.retrace_path(__lowerCAmelCase  )
														bwd_path.pop()
														bwd_path.reverse()
														UpperCamelCase__				     =			fwd_path + bwd_path
														return path


if __name__ == "__main__":
					# all coordinates are given in format [y,x]
					import doctest

					doctest.testmod()
					UpperCamelCase__											= (0, 0)
					UpperCamelCase__											= (len(grid) - 1, len(grid[0]) - 1)
					for elem in grid:
										print(elem)

					UpperCamelCase__											= time.time()
					UpperCamelCase__											= BreadthFirstSearch(init, goal)
					UpperCamelCase__											= bfs.search()
					UpperCamelCase__											= time.time() - start_bfs_time

					print("Unidirectional BFS computation time : ", bfs_time)

					UpperCamelCase__											= time.time()
					UpperCamelCase__											= BidirectionalBreadthFirstSearch(init, goal)
					UpperCamelCase__											= bd_bfs.search()
					UpperCamelCase__											= time.time() - start_bd_bfs_time

					print("Bidirectional BFS computation time : ", bd_bfs_time)











import math





def     _UpperCamelCase     (a__   :int       ):






							"""simple docstring"""





							UpperCamelCase__				     =			[True] * n
							UpperCamelCase__				     =			False
							UpperCamelCase__				     =			False
							UpperCamelCase__				     =			True

							for i in range(3   ,			int(n**0.5 + 1       )   ,			2       ):
														UpperCamelCase__				     =			i * 2
														while index < n:
																					UpperCamelCase__				     =			False
																					UpperCamelCase__				     =			index + i

							UpperCamelCase__				     =			[2]

							for i in range(3   ,			a__   ,			2       ):
														if is_prime[i]:
																					primes.append(a__       )

							return primes





def     _UpperCamelCase     (a__   :int = 9999_6666_3333       ):






							"""simple docstring"""





							UpperCamelCase__				     =			math.floor(math.sqrt(a__       )       ) + 100
							UpperCamelCase__				     =			prime_sieve(a__       )

							UpperCamelCase__				     =			0
							UpperCamelCase__				     =			0
							UpperCamelCase__				     =			primes[prime_index]

							while (last_prime**2) <= limit:
														UpperCamelCase__				     =			primes[prime_index + 1]

														UpperCamelCase__				     =			last_prime**2
														UpperCamelCase__				     =			next_prime**2

														# Get numbers divisible by lps(current)
														UpperCamelCase__				     =			lower_bound + last_prime
														while upper_bound > current <= limit:
																					matches_sum += current
																					current += last_prime

														# Reset the upper_bound
														while (upper_bound - next_prime) > limit:
																					upper_bound -= next_prime

														# Add the numbers divisible by ups(current)
														UpperCamelCase__				     =			upper_bound - next_prime
														while current > lower_bound:
																					matches_sum += current
																					current -= next_prime

														# Remove the numbers divisible by both ups and lps
														UpperCamelCase__				     =			0
														while upper_bound > current <= limit:
																					if current <= lower_bound:
																												# Increment the current number
																												current += last_prime * next_prime
																												continue

																					if current > limit:
																												break

																					# Remove twice since it was added by both ups and lps
																					matches_sum -= current * 2

																					# Increment the current number
																					current += last_prime * next_prime

														# Setup for next pair
														UpperCamelCase__				     =			next_prime
														prime_index += 1

							return matches_sum


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




