






from __future__ import annotations

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

SCREAMING_SNAKE_CASE__				     =			TypeVar('''T''')






class 			_UpperCamelCase(       Generic[T]		):

		def __init__(					self		:    str    ,       SCREAMING_SNAKE_CASE__		:    list[T]    ,       SCREAMING_SNAKE_CASE__		:    Callable[[T, T], T]    ):



					'''simple docstring'''



					__a						:  Any | T									=     None

					__a						:  int									=     len(SCREAMING_SNAKE_CASE__    )
					__a						:  list[T]									=     [any_type for _ in range(self.N    )] + arr
					__a						:  List[Any]									=     fnc
					self.build()

		def    __lowerCAmelCase  (					self		:    int    ):



					'''simple docstring'''



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

		def    __lowerCAmelCase  (					self		:    Tuple    ,       SCREAMING_SNAKE_CASE__		:    int    ,       SCREAMING_SNAKE_CASE__		:    T    ):



					'''simple docstring'''



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



		def    __lowerCAmelCase  (					self		:    List[str]    ,       SCREAMING_SNAKE_CASE__		:    int    ,       SCREAMING_SNAKE_CASE__		:    int    ):  # noqa: E741



					'''simple docstring'''



					__a						,					__a						:  Any									=     l + self.N, r + self.N

					__a						:  T | None									=     None
					while l <= r:
								if l % 2 == 1:
											__a						:  str									=     self.st[l] if res is None else self.fn(SCREAMING_SNAKE_CASE__    ,       self.st[l]    )
								if r % 2 == 0:
											__a						:  List[Any]									=     self.st[r] if res is None else self.fn(SCREAMING_SNAKE_CASE__    ,       self.st[r]    )
								__a						,					__a						:  Optional[Any]									=     (l + 1) // 2, (r - 1) // 2
					return res


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

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

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

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

							def        UpperCAmelCase__		(						):
										for i in range(len(lowerCamelCase_				)				):
													for j in range(lowerCamelCase_   ,  len(lowerCamelCase_				)				):
																__a						:  str									=     reduce(lowerCamelCase_   ,  test_array[i : j + 1]				)
																__a						:  Tuple									=     reduce(lowerCamelCase_   ,  test_array[i : j + 1]				)
																__a						:  Optional[int]									=     reduce(lambda lowerCamelCase_   ,  lowerCamelCase_				: a + b   ,  test_array[i : j + 1]				)
																assert min_range == min_segment_tree.query(lowerCamelCase_   ,  lowerCamelCase_				)
																assert max_range == max_segment_tree.query(lowerCamelCase_   ,  lowerCamelCase_				)
																assert sum_range == sum_segment_tree.query(lowerCamelCase_   ,  lowerCamelCase_				)

							test_all_segments()

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











def      lowerCamelCase_						(			)	->			List[str]:





				"""simple docstring"""


				__lowerCamelCase									=       0
				for i in range(1					,	1001 ):
								total += i**i
				return str(UpperCamelCase__ )[-10:]


if __name__ == "__main__":
					print(solution())


