






from __future__ import annotations

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

lowerCAmelCase_	:    Optional[int]            =      TypeVar('''T''')





class   UpperCamelCase_ (       Generic[T]  ):



  def __init__(      self ,		snake_case__ ,		snake_case__				)			->			None:



         """simple docstring"""





         UpperCAmelCase	    =			None

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



  def 		UpperCamelCase_				(      self				)			->			None:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__ ,		snake_case__				)			->			None:



         """simple docstring"""





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



  def 		UpperCamelCase_				(      self ,		snake_case__ ,		snake_case__				)			->			T | None:  # noqa: E741



         """simple docstring"""





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

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


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

 lowerCAmelCase_	:    Optional[int]            =      [1, 1_0, -2, 9, -3, 8, 4, -7, 5, 6, 1_1, -1_2]

 lowerCAmelCase_	:    Tuple            =      {
     0: 7,
     1: 2,
     2: 6,
     3: -1_4,
     4: 5,
     5: 4,
     6: 7,
     7: -1_0,
     8: 9,
     9: 1_0,
     1_0: 1_2,
     1_1: 1,
 }

 lowerCAmelCase_	:    Union[str, Any]            =      SegmentTree(test_array, min)
 lowerCAmelCase_	:    Optional[Any]            =      SegmentTree(test_array, max)
 lowerCAmelCase_	:    str            =      SegmentTree(test_array, lambda a, b: a + b)






 def       _lowerCAmelCase       (      ):







        '''simple docstring'''



        for i in range(len(lowerCAmelCase		)		):
               for j in range(lowerCAmelCase	,      len(lowerCAmelCase		)		):
                      UpperCAmelCase	    =			reduce(lowerCAmelCase	,      test_array[i : j + 1]		)
                      UpperCAmelCase	    =			reduce(lowerCAmelCase	,      test_array[i : j + 1]		)
                      UpperCAmelCase	    =			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():
  lowerCAmelCase_	:    List[str]            =      value
  min_segment_tree.update(index, value)
  max_segment_tree.update(index, value)
  sum_segment_tree.update(index, value)
  test_all_segments()








"""simple docstring"""







def       _lowerCAmelCase       (      lowerCAmelCase		):







       '''simple docstring'''
       if not isinstance(lowerCAmelCase	,      lowerCAmelCase		):
              UpperCAmelCase	    =			F'''Input value of [number={number}] must be an integer'''
              raise TypeError(lowerCAmelCase		)
       if number < 0:
              return False
       UpperCAmelCase	    =			number * number
       while number > 0:
              if number % 10 != number_square % 10:
                     return False
              number //= 10
              number_square //= 10
       return True


if __name__ == "__main__":
 import doctest

 doctest.testmod()
