from __future__ import annotations

from collections.abc import Callable
from typing import Any, Generic, TypeVar

A_      =      TypeVar("T")






class      __lowercase					(    Generic[T]    ):

      def __init__(	self				:      Dict							,							__lowerCamelCase				:      list[T]							,							__lowerCamelCase				:      Callable[[T, T], T]   )							->		None:


         '''simple docstring'''

         lowercase							=		None

         lowercase							=		len(__lowerCamelCase   )
         lowercase							=		[any_type for _ in range(self.N   )] + arr
         lowercase							=		fnc
         self.build()

      def        __a		(	self				:      List[Any]   )							->		None:


         '''simple docstring'''

         for p in range(self.N - 1							,							0							,							-1   ):
            lowercase							=		self.fn(self.st[p * 2]							,							self.st[p * 2 + 1]   )

      def        __a		(	self				:      Tuple							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      T   )							->		None:


         '''simple docstring'''

         p += self.N
         lowercase							=		v
         while p > 1:
            lowercase							=		p // 2
            lowercase							=		self.fn(self.st[p * 2]							,							self.st[p * 2 + 1]   )



      def        __a		(	self				:      List[str]							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      int   )							->		T | None:  # noqa: E741


         '''simple docstring'''

         lowercase		,lowercase							=		l + self.N, r + self.N

         lowercase							=		None
         while l <= r:
            if l % 2 == 1:
               lowercase							=		self.st[l] if res is None else self.fn(__lowerCamelCase							,							self.st[l]   )
            if r % 2 == 0:
               lowercase							=		self.st[r] if res is None else self.fn(__lowerCamelCase							,							self.st[r]   )
            lowercase		,lowercase							=		(l + 1) // 2, (r - 1) // 2
         return res


if __name__ == "__main__":
      from functools import reduce

      A_      =      [1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]

      A_      =      {
          0: 7,
          1: 2,
          2: 6,
          3: -14,
          4: 5,
          5: 4,
          6: 7,
          7: -10,
          8: 9,
          9: 10,
          10: 12,
          11: 1,
      }

      A_      =      SegmentTree(test_array, min)
      A_      =      SegmentTree(test_array, max)
      A_      =      SegmentTree(test_array, lambda a, b: a + b)






      def        __UpperCAmelCase    (       )->       None:



         """simple docstring"""







         for i in range(len(UpperCAmelCase       )       ):
            for j in range(UpperCAmelCase,		len(UpperCAmelCase       )       ):
               lowercase							=		reduce(UpperCAmelCase,		test_array[i : j + 1]       )
               lowercase							=		reduce(UpperCAmelCase,		test_array[i : j + 1]       )
               lowercase							=		reduce(lambda UpperCAmelCase,		UpperCAmelCase       : a + b,		test_array[i : j + 1]       )
               assert min_range == min_segment_tree.query(UpperCAmelCase,		UpperCAmelCase       )
               assert max_range == max_segment_tree.query(UpperCAmelCase,		UpperCAmelCase       )
               assert sum_range == sum_segment_tree.query(UpperCAmelCase,		UpperCAmelCase       )

      test_all_segments()

      for index, value in test_updates.items():
            A_      =      value
            min_segment_tree.update(index, value)
            max_segment_tree.update(index, value)
            sum_segment_tree.update(index, value)
            test_all_segments()






from __future__ import annotations

import math






def        __UpperCAmelCase    (       UpperCAmelCase       )->       list[int]:



			"""simple docstring"""







			if num <= 0:
						lowercase							=		f'{num}: Invalid input, please enter a positive integer.'
						raise ValueError(UpperCAmelCase       )

			lowercase							=		[True] * (num + 1)
			lowercase							=		[]
			lowercase							=		2
			lowercase							=		int(math.sqrt(UpperCAmelCase       )       )

			while start <= end:
						# If start is a prime
						if sieve[start] is True:
									prime.append(UpperCAmelCase       )

									# Set multiples of start be False
									for i in range(start * start,		num + 1,		UpperCAmelCase       ):
												if sieve[i] is True:
															lowercase							=		False

						start += 1

			for j in range(end + 1,		num + 1       ):
						if sieve[j] is True:
									prime.append(UpperCAmelCase       )

			return prime


if __name__ == "__main__":
						print(prime_sieve(int(input("Enter a positive integer: ").strip())))





