




from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any




class 	UpperCamelCase__			:

    '''simple docstring'''



    lowerCamelCase_   :			List[str]			  =   ('_front', '_back', '_len')




    @dataclass
    class 	UpperCamelCase__			:

        '''simple docstring'''



        lowerCamelCase_   :			Any			  =   None
        lowerCamelCase_   :			Deque._Node | None			  =   None
        lowerCamelCase_   :			Deque._Node | None			  =   None




    class 	UpperCamelCase__			:

        '''simple docstring'''



        lowerCamelCase_   :			Any			  =   ('_cur',)







        def __init__(					self  ,						UpperCamelCase__  )  ->   None:
               lowerCamelCase     :   Any    				=      cur







        def __iter__(					self  )  ->   Deque._Iterator:
               return self







        def 					_lowercase  (					self  )  ->   Any:
               if self._cur is None:
                      # finished iterating
                      raise StopIteration
               lowerCamelCase     :   List[Any]    				=      self._cur.val
               lowerCamelCase     :   List[Any]    				=      self._cur.next_node

               return val







    def __init__(					self  ,						UpperCamelCase__ = None  )  ->   None:
           lowerCamelCase     :   Any    				=      None
           lowerCamelCase     :   Any    				=      None
           lowerCamelCase     :   int    				=      0

           if iterable is not None:
                  # append every value to the deque
                  for val in iterable:
                         self.append(_snake_case  )







    def 					_lowercase  (					self  ,						UpperCamelCase__  )  ->   None:
           lowerCamelCase     :   List[str]    				=      self._Node(_snake_case  ,						_snake_case  ,						_snake_case  )
           if self.is_empty():
                  # front = back
                  lowerCamelCase     :   Union[str, Any]    				=      node
                  lowerCamelCase     :   Tuple    				=      1
           else:
                  # connect nodes
                  lowerCamelCase     :   Union[str, Any]    				=      node
                  lowerCamelCase     :   int    				=      self._back
                  lowerCamelCase     :   List[Any]    				=      node  # assign new back to the new node

                  self._len += 1

                  # make sure there were no errors
                  assert not self.is_empty(), "Error on appending value."







    def 					_lowercase  (					self  ,						UpperCamelCase__  )  ->   None:
           lowerCamelCase     :   Optional[Any]    				=      self._Node(_snake_case  ,						_snake_case  ,						_snake_case  )
           if self.is_empty():
                  # front = back
                  lowerCamelCase     :   Union[str, Any]    				=      node
                  lowerCamelCase     :   Optional[int]    				=      1
           else:
                  # connect nodes
                  lowerCamelCase     :   Tuple    				=      self._front
                  lowerCamelCase     :   Optional[int]    				=      node
                  lowerCamelCase     :   List[str]    				=      node  # assign new front to the new node

                  self._len += 1

                  # make sure there were no errors
                  assert not self.is_empty(), "Error on appending value."







    def 					_lowercase  (					self  ,						UpperCamelCase__  )  ->   None:
           for val in iterable:
                  self.append(_snake_case  )







    def 					_lowercase  (					self  ,						UpperCamelCase__  )  ->   None:
           for val in iterable:
                  self.appendleft(_snake_case  )







    def 					_lowercase  (					self  )  ->   Any:
           assert not self.is_empty(), "Deque is empty."

           lowerCamelCase     :   int    				=      self._back
           lowerCamelCase     :   List[Any]    				=      self._back.prev_node  # set new back
           # drop the last node - python will deallocate memory automatically
           lowerCamelCase     :   Union[str, Any]    				=      None

           self._len -= 1

           return topop.val







    def 					_lowercase  (					self  )  ->   Any:
           assert not self.is_empty(), "Deque is empty."

           lowerCamelCase     :   List[Any]    				=      self._front
           lowerCamelCase     :   str    				=      self._front.next_node  # set new front and drop the first node
           lowerCamelCase     :   Union[str, Any]    				=      None

           self._len -= 1

           return topop.val







    def 					_lowercase  (					self  )  ->   bool:
           return self._front is None







    def __len__(					self  )  ->   int:
           return self._len







    def __eq__(					self  ,						UpperCamelCase__  )  ->   bool:

           if not isinstance(_snake_case  ,						_snake_case  ):
                  return NotImplemented

           lowerCamelCase     :   Optional[int]    				=      self._front
           lowerCamelCase     :   List[Any]    				=      other._front

           # if the length of the dequeues are not the same, they are not equal
           if len(self  ) != len(_snake_case  ):
                  return False

           while me is not None and oth is not None:
                  # compare every value
                  if me.val != oth.val:
                         return False
                  lowerCamelCase     :   str    				=      me.next_node
                  lowerCamelCase     :   List[str]    				=      oth.next_node

           return True







    def __iter__(					self  )  ->   Deque._Iterator:
           return Deque._Iterator(self._front  )







    def __repr__(					self  )  ->   str:
           lowerCamelCase     :   str    				=      []
           lowerCamelCase     :   Tuple    				=      self._front
           while aux is not None:
                  # append the values in a list to display
                  values_list.append(aux.val  )
                  lowerCamelCase     :   List[str]    				=      aux.next_node

           return F'''[{", ".join(repr(_snake_case  ) for val in values_list  )}]'''


if __name__ == "__main__":
       import doctest

       doctest.testmod()












from itertools import compress, repeat
from math import ceil, sqrt

def   A   (   _SCREAMING_SNAKE_CASE					)			->				list[int]:

       if num <= 2:
              return []
       if num == 3:
              return [2]

       # Odd sieve for numbers in range [3, num - 1]
       lowerCamelCase     :   str    				=      bytearray(B"\x01"					) * ((num >> 1) - 1)

       for i in range(3				,int(sqrt(_SCREAMING_SNAKE_CASE					)					) + 1				,2					):
              if sieve[(i >> 1) - 1]:
                     lowerCamelCase     :   Tuple    				=      i**2
                     lowerCamelCase     :   str    				=      repeat(
                         0				,ceil((num - i_squared) / (i << 1)					)					)

       return [2] + list(compress(range(3				,_SCREAMING_SNAKE_CASE				,2					)				,_SCREAMING_SNAKE_CASE					)					)


if __name__ == "__main__":
       import doctest

       doctest.testmod()






