






from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
snake_case     					=		0

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

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

snake_case     					=		tuple[int, int]


class 			SCREAMING_SNAKE_CASE      :
     '''simple docstring'''


     def __init__(					self							:						Optional[int]       ,			UpperCAmelCase_							:						int       ,			UpperCAmelCase_							:						int       ,			UpperCAmelCase_							:						int       ,			UpperCAmelCase_							:						int       ,			UpperCAmelCase_							:						int       ,			UpperCAmelCase_							:						Node | None       ,			):
       SCREAMING_SNAKE_CASE							:   Union[str, Any]						    =     pos_x
       SCREAMING_SNAKE_CASE							:   Any						    =     pos_y
       SCREAMING_SNAKE_CASE							:   Optional[Any]						    =     (pos_y, pos_x)
       SCREAMING_SNAKE_CASE							:   Any						    =     goal_x
       SCREAMING_SNAKE_CASE							:   Optional[Any]						    =     goal_y
       SCREAMING_SNAKE_CASE							:   Dict						    =     g_cost
       SCREAMING_SNAKE_CASE							:   int						    =     parent
       SCREAMING_SNAKE_CASE							:   int						    =     self.calculate_heuristic()
       SCREAMING_SNAKE_CASE							:   List[Any]						    =     self.g_cost + self.h_cost


     def 					_A							(					self							:						Union[str, Any]   ):
       SCREAMING_SNAKE_CASE							:   Optional[int]						    =     self.pos_x - self.goal_x
       SCREAMING_SNAKE_CASE							:   Optional[int]						    =     self.pos_y - self.goal_y
       if HEURISTIC == 1:
         return abs(UpperCAmelCase_   ) + abs(UpperCAmelCase_   )
       else:
         return sqrt(dy**2 + dx**2   )






     def __lt__(					self							:						Union[str, Any]       ,			UpperCAmelCase_							:						Node   ):
       return self.f_cost < other.f_cost





class 			SCREAMING_SNAKE_CASE      :
     '''simple docstring'''


     def __init__(					self							:						Union[str, Any]       ,			UpperCAmelCase_							:						TPosition       ,			UpperCAmelCase_							:						TPosition   ):
       SCREAMING_SNAKE_CASE							:   List[Any]						    =     Node(start[1]       ,			start[0]       ,			goal[1]       ,			goal[0]       ,			0       ,			UpperCAmelCase_   )
       SCREAMING_SNAKE_CASE							:   Optional[int]						    =     Node(goal[1]       ,			goal[0]       ,			goal[1]       ,			goal[0]       ,			9_9999       ,			UpperCAmelCase_   )

       SCREAMING_SNAKE_CASE							:   List[str]						    =     [self.start]
       SCREAMING_SNAKE_CASE							:   list[Node]						    =     []

       SCREAMING_SNAKE_CASE							:   Tuple						    =     False


     def 					_A							(					self							:						Union[str, Any]   ):
       while self.open_nodes:
         # Open Nodes are sorted using __lt__
         self.open_nodes.sort()
         SCREAMING_SNAKE_CASE							:   List[Any]						    =     self.open_nodes.pop(0   )

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

         self.closed_nodes.append(UpperCAmelCase_   )
         SCREAMING_SNAKE_CASE							:   Tuple						    =     self.get_successors(UpperCAmelCase_   )

         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(UpperCAmelCase_   )
           else:
             # retrieve the best current path
             SCREAMING_SNAKE_CASE							:   Union[str, Any]						    =     self.open_nodes.pop(self.open_nodes.index(UpperCAmelCase_   )   )

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

       return [self.start.pos]


     def 					_A							(					self							:						List[Any]       ,			UpperCAmelCase_							:						Node   ):
       SCREAMING_SNAKE_CASE							:   int						    =     []
       for action in delta:
         SCREAMING_SNAKE_CASE							:   Optional[Any]						    =     parent.pos_x + action[1]
         SCREAMING_SNAKE_CASE							:   Any						    =     parent.pos_y + action[0]
         if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(UpperCAmelCase_   ) - 1):
           continue

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

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






     def 					_A							(					self							:						str       ,			UpperCAmelCase_							:						Node | None   ):
       SCREAMING_SNAKE_CASE							:   List[Any]						    =     node
       SCREAMING_SNAKE_CASE							:   Optional[Any]						    =     []
       while current_node is not None:
         path.append((current_node.pos_y, current_node.pos_x)   )
         SCREAMING_SNAKE_CASE							:   Optional[int]						    =     current_node.parent
       path.reverse()
       return path





class 			SCREAMING_SNAKE_CASE      :
     '''simple docstring'''


     def __init__(					self							:						List[str]       ,			UpperCAmelCase_							:						TPosition       ,			UpperCAmelCase_							:						TPosition   ):
       SCREAMING_SNAKE_CASE							:   List[str]						    =     AStar(UpperCAmelCase_       ,			UpperCAmelCase_   )
       SCREAMING_SNAKE_CASE							:   int						    =     AStar(UpperCAmelCase_       ,			UpperCAmelCase_   )
       SCREAMING_SNAKE_CASE							:   str						    =     False


     def 					_A							(					self							:						List[Any]   ):
       while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
         self.fwd_astar.open_nodes.sort()
         self.bwd_astar.open_nodes.sort()
         SCREAMING_SNAKE_CASE							:   Optional[int]						    =     self.fwd_astar.open_nodes.pop(0   )
         SCREAMING_SNAKE_CASE							:   Dict						    =     self.bwd_astar.open_nodes.pop(0   )

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

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

         SCREAMING_SNAKE_CASE							:   Tuple						    =     current_bwd_node
         SCREAMING_SNAKE_CASE							:   Tuple						    =     current_fwd_node

         SCREAMING_SNAKE_CASE							:   Optional[int]						    =     {
             self.fwd_astar: self.fwd_astar.get_successors(UpperCAmelCase_   ),
             self.bwd_astar: self.bwd_astar.get_successors(UpperCAmelCase_   ),
         }

         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(UpperCAmelCase_   )
             else:
               # retrieve the best current path
               SCREAMING_SNAKE_CASE							:   Optional[int]						    =     astar.open_nodes.pop(
                   astar.open_nodes.index(UpperCAmelCase_   )   )

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

       return [self.fwd_astar.start.pos]






     def 					_A							(					self							:						Any       ,			UpperCAmelCase_							:						Node       ,			UpperCAmelCase_							:						Node   ):
       SCREAMING_SNAKE_CASE							:   str						    =     self.fwd_astar.retrace_path(UpperCAmelCase_   )
       SCREAMING_SNAKE_CASE							:   List[str]						    =     self.bwd_astar.retrace_path(UpperCAmelCase_   )
       bwd_path.pop()
       bwd_path.reverse()
       SCREAMING_SNAKE_CASE							:   List[Any]						    =     fwd_path + bwd_path
       return path


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

   snake_case     					=		time.time()
   snake_case     					=		AStar(init, goal)
   snake_case     					=		a_star.search()
   snake_case     					=		time.time() - start_time
   print(F"""AStar execution time = {end_time:f} seconds""")

   snake_case     					=		time.time()
   snake_case     					=		BidirectionalAStar(init, goal)
   snake_case     					=		time.time() - bd_start_time
   print(F"""BidirectionalAStar execution time = {bd_end_time:f} seconds""")









import math


def 							__lowerCAmelCase     (							_UpperCamelCase		:	int						)		->				list[int]:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE		    =      []
 SCREAMING_SNAKE_CASE		    =      2
 SCREAMING_SNAKE_CASE		    =      int(math.sqrt(_UpperCamelCase						)						)  # Size of every segment
 SCREAMING_SNAKE_CASE		    =      [True] * (end + 1)
 SCREAMING_SNAKE_CASE		    =      []

 while start <= end:
  if temp[start] is True:
   in_prime.append(_UpperCamelCase						)
   for i in range(start * start		,				end + 1		,				_UpperCamelCase						):
    SCREAMING_SNAKE_CASE		    =      False
  start += 1
 prime += in_prime

 SCREAMING_SNAKE_CASE		    =      end + 1
 SCREAMING_SNAKE_CASE		    =      min(2 * end		,				_UpperCamelCase						)

 while low <= n:
  SCREAMING_SNAKE_CASE		    =      [True] * (high - low + 1)
  for each in in_prime:
   SCREAMING_SNAKE_CASE		    =      math.floor(low / each						) * each
   if t < low:
    t += each

   for j in range(_UpperCamelCase		,				high + 1		,				_UpperCamelCase						):
    SCREAMING_SNAKE_CASE		    =      False

  for j in range(len(_UpperCamelCase						)						):
   if temp[j] is True:
    prime.append(j + low						)

  SCREAMING_SNAKE_CASE		    =      high + 1
  SCREAMING_SNAKE_CASE		    =      min(high + end		,				_UpperCamelCase						)

 return prime




print(sieve(10**6))

