

"""simple docstring"""
from __future__ import annotations

import time

_A							=  list[tuple[int, int]]

_A							=  [
    [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							=  [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class       lowerCamelCase	:


  '''simple docstring'''







  def __init__(self							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

        UpperCAmelCase__			:							Dict							=    pos_x
        UpperCAmelCase__			:							Tuple							=    pos_y
        UpperCAmelCase__			:							Union[str, Any]							=    (pos_y, pos_x)
        UpperCAmelCase__			:							Optional[Any]							=    goal_x
        UpperCAmelCase__			:							Tuple							=    goal_y
        UpperCAmelCase__			:							List[Any]							=    parent




class       lowerCamelCase	:


  '''simple docstring'''







  def __init__(self							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

        UpperCAmelCase__			:							Union[str, Any]							=    Node(start[1]							,       start[0]							,       goal[1]							,       goal[0]							,       _lowerCamelCase	)
        UpperCAmelCase__			:							Union[str, Any]							=    Node(goal[1]							,       goal[0]							,       goal[1]							,       goal[0]							,       _lowerCamelCase	)

        UpperCAmelCase__			:							List[Any]							=    [self.start]
        UpperCAmelCase__			:							Tuple							=    False



  def  _a      (self	):


        """simple docstring"""

        while self.node_queue:
              UpperCAmelCase__			:							int							=    self.node_queue.pop(0	)

              if current_node.pos == self.target.pos:
                    UpperCAmelCase__			:							Dict							=    True
                    return self.retrace_path(_lowerCamelCase	)

              UpperCAmelCase__			:							Union[str, Any]							=    self.get_successors(_lowerCamelCase	)

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

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



  def  _a      (self							,       _lowerCamelCase	):


        """simple docstring"""

        UpperCAmelCase__			:							str							=    []
        for action in delta:
              UpperCAmelCase__			:							Union[str, Any]							=    parent.pos_x + action[1]
              UpperCAmelCase__			:							str							=    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  _a      (self							,       _lowerCamelCase	):


        """simple docstring"""

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




class       lowerCamelCase	:


  '''simple docstring'''







  def __init__(self							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

        UpperCAmelCase__			:							Dict							=    BreadthFirstSearch(_lowerCamelCase							,       _lowerCamelCase	)
        UpperCAmelCase__			:							Optional[int]							=    BreadthFirstSearch(_lowerCamelCase							,       _lowerCamelCase	)
        UpperCAmelCase__			:							Tuple							=    False



  def  _a      (self	):


        """simple docstring"""

        while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
              UpperCAmelCase__			:							Any							=    self.fwd_bfs.node_queue.pop(0	)
              UpperCAmelCase__			:							Union[str, Any]							=    self.bwd_bfs.node_queue.pop(0	)

              if current_bwd_node.pos == current_fwd_node.pos:
                    UpperCAmelCase__			:							Optional[int]							=    True
                    return self.retrace_bidirectional_path(
                        _lowerCamelCase							,       _lowerCamelCase	)

              UpperCAmelCase__			:							Dict							=    current_bwd_node
              UpperCAmelCase__			:							Any							=    current_fwd_node

              UpperCAmelCase__			:							List[Any]							=    {
                  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  _a      (self							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

        UpperCAmelCase__			:							List[Any]							=    self.fwd_bfs.retrace_path(_lowerCamelCase	)
        UpperCAmelCase__			:							Dict							=    self.bwd_bfs.retrace_path(_lowerCamelCase	)
        bwd_path.pop()
        bwd_path.reverse()
        UpperCAmelCase__			:							Optional[int]							=    fwd_path + bwd_path
        return path


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

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

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

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

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

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




"""simple docstring"""
import math




def 					a__						(						lowerCAmelCase    )	-> list[int]:
      UpperCAmelCase__			:							Optional[int]							=    []
      UpperCAmelCase__			:							Union[str, Any]							=    2
      UpperCAmelCase__			:							List[Any]							=    int(math.sqrt(lowerCAmelCase    )    )  # Size of every segment
      UpperCAmelCase__			:							Dict							=    [True] * (end + 1)
      UpperCAmelCase__			:							str							=    []

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

      UpperCAmelCase__			:							Optional[Any]							=    end + 1
      UpperCAmelCase__			:							Dict							=    min(2 * end			,	lowerCAmelCase    )

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

                  for j in range(lowerCAmelCase			,	high + 1			,	lowerCAmelCase    ):
                        UpperCAmelCase__			:							int							=    False

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

            UpperCAmelCase__			:							Dict							=    high + 1
            UpperCAmelCase__			:							int							=    min(high + end			,	lowerCAmelCase    )

      return prime





print(sieve(10**6))

