


from __future__ import annotations

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







class   __lowercase						:





							"""simple docstring"""







							_UpperCAmelCase						     =	('_front', '_back', '_len')







							@dataclass
							class   __lowercase						:





														"""simple docstring"""







														_UpperCAmelCase						     =	None
														_UpperCAmelCase						     =	None
														_UpperCAmelCase						     =	None







							class   __lowercase						:





														"""simple docstring"""







														_UpperCAmelCase						     =	('_cur',)






														def __init__(			self ,	lowerCAmelCase__					):





																	"""simple docstring"""




																	SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				cur






														def __iter__(			self					):





																	"""simple docstring"""




																	return self






														def 				UpperCamelCase__    (			self					):





																	"""simple docstring"""




																	if self._cur is None:
																				# finished iterating
																				raise StopIteration
																	SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				self._cur.val
																	SCREAMING_SNAKE_CASE_		:    Any 		=				self._cur.next_node

																	return val







							def __init__(			self ,	lowerCAmelCase__ = None					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				None
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				None
										SCREAMING_SNAKE_CASE_		:    Dict 		=				0

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






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				self._Node(a_ ,	a_ ,	a_					)
										if self.is_empty():
													# front = back
													SCREAMING_SNAKE_CASE_		:    Any 		=				node
													SCREAMING_SNAKE_CASE_		:    str 		=				1
										else:
													# connect nodes
													SCREAMING_SNAKE_CASE_		:    str 		=				node
													SCREAMING_SNAKE_CASE_		:    Tuple 		=				self._back
													SCREAMING_SNAKE_CASE_		:    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 				UpperCamelCase__    (			self ,	lowerCAmelCase__					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Dict 		=				self._Node(a_ ,	a_ ,	a_					)
										if self.is_empty():
													# front = back
													SCREAMING_SNAKE_CASE_		:    int 		=				node
													SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				1
										else:
													# connect nodes
													SCREAMING_SNAKE_CASE_		:    Any 		=				self._front
													SCREAMING_SNAKE_CASE_		:    Any 		=				node
													SCREAMING_SNAKE_CASE_		:    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 				UpperCamelCase__    (			self ,	lowerCAmelCase__					):





										"""simple docstring"""




										for val in iterable:
													self.append(a_					)






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__					):





										"""simple docstring"""




										for val in iterable:
													self.appendleft(a_					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										assert not self.is_empty(), "Deque is empty."

										SCREAMING_SNAKE_CASE_		:    str 		=				self._back
										SCREAMING_SNAKE_CASE_		:    str 		=				self._back.prev_node  # set new back
										# drop the last node - python will deallocate memory automatically
										SCREAMING_SNAKE_CASE_		:    Dict 		=				None

										self._len -= 1

										return topop.val






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										assert not self.is_empty(), "Deque is empty."

										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				self._front
										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				self._front.next_node  # set new front and drop the first node
										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				None

										self._len -= 1

										return topop.val






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										return self._front is None






							def __len__(			self					):





										"""simple docstring"""




										return self._len






							def __eq__(			self ,	lowerCAmelCase__					):





										"""simple docstring"""




										if not isinstance(a_ ,	a_					):
													return NotImplemented

										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				self._front
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				other._front

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

										while me is not None and oth is not None:
													# compare every value
													if me.val != oth.val:
																return False
													SCREAMING_SNAKE_CASE_		:    Tuple 		=				me.next_node
													SCREAMING_SNAKE_CASE_		:    Any 		=				oth.next_node

										return True






							def __iter__(			self					):





										"""simple docstring"""




										return Deque._Iterator(self._front					)






							def __repr__(			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Tuple 		=				[]
										SCREAMING_SNAKE_CASE_		:    Dict 		=				self._front
										while aux is not None:
													# append the values in a list to display
													values_list.append(aux.val					)
													SCREAMING_SNAKE_CASE_		:    str 		=				aux.next_node

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


if __name__ == "__main__":
				import doctest

				doctest.testmod()



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






def 	a__ (							A__							):

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

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

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

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


if __name__ == "__main__":
				import doctest

				doctest.testmod()





