
'''simple docstring'''



from __future__ import annotations

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

UpperCamelCase__      :		List[Any]       							=  TypeVar("T")

class    _a				(Generic[T]):





       """simple docstring"""




       def __init__(							self       ,							A__       ,							A__      )    ->			None:
          _SCREAMING_SNAKE_CASE      =				None

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






       def        UpperCamelCase				(							self      )    ->			None:
          for p in range(self.N - 1       ,							0       ,							-1      ):
             _SCREAMING_SNAKE_CASE      =				self.fn(self.st[p * 2]       ,							self.st[p * 2 + 1]      )






       def        UpperCamelCase				(							self       ,							A__       ,							A__      )    ->			None:
          p += self.N
          _SCREAMING_SNAKE_CASE      =				v
          while p > 1:
             _SCREAMING_SNAKE_CASE      =				p // 2
             _SCREAMING_SNAKE_CASE      =				self.fn(self.st[p * 2]       ,							self.st[p * 2 + 1]      )






       def        UpperCamelCase				(							self       ,							A__       ,							A__      )    ->			T | None:  # noqa: E741
          _SCREAMING_SNAKE_CASE ,							_SCREAMING_SNAKE_CASE      =				l + self.N, r + self.N

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


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

     UpperCamelCase__      :		Optional[int]       							=  [1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]

     UpperCamelCase__      :		Union[str, Any]       							=  {
         0: 7,
         1: 2,
         2: 6,
         3: -14,
         4: 5,
         5: 4,
         6: 7,
         7: -10,
         8: 9,
         9: 10,
         10: 12,
         11: 1,
     }

     UpperCamelCase__      :		List[str]       							=  SegmentTree(test_array, min)
     UpperCamelCase__      :		List[Any]       							=  SegmentTree(test_array, max)
     UpperCamelCase__      :		Optional[Any]       							=  SegmentTree(test_array, lambda a, b: a + b)
     def    lowerCAmelCase_	(				)     ->     None:




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

     test_all_segments()

     for index, value in test_updates.items():
          UpperCamelCase__      :		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_	(				SCREAMING_SNAKE_CASE_						)     ->     str:




   """simple docstring"""
   return "".join([hex(SCREAMING_SNAKE_CASE_						)[2:].zfill(2						).upper() for byte in list(SCREAMING_SNAKE_CASE_						)]						)
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_						)     ->     bytes:




   """simple docstring"""
   # Check data validity, following RFC3548
   # https://www.ietf.org/rfc/rfc3548.txt
   if (len(SCREAMING_SNAKE_CASE_						) % 2) != 0:
      raise ValueError(
          """Base16 encoded data is invalid:
Data does not have an even number of hex digits."""						)
   # Check the character set - the standard base16 alphabet
   # is uppercase according to RFC3548 section 6
   if not set(SCREAMING_SNAKE_CASE_						) <= set("""0123456789ABCDEF"""						):
      raise ValueError(
          """Base16 encoded data is invalid:
Data is not uppercase hex or it contains invalid characters."""						)
   # For every two hexadecimal digits (= a byte), turn it into an integer.
   # Then, string the result together into bytes, and return it.
   return bytes(int(data[i] + data[i + 1]    ,      16						) for i in range(0    ,      len(SCREAMING_SNAKE_CASE_						)    ,      2						)						)


if __name__ == "__main__":
     import doctest

     doctest.testmod()






