






import math







class       UpperCAmelCase_						:



      """simple docstring"""
      def __init__(    self   ,    SCREAMING_SNAKE_CASE_			)    ->				Dict:
          UpperCamelCase	:Any     							=       len(SCREAMING_SNAKE_CASE_			)
          UpperCamelCase	:Optional[int]     							=       [0] * (
              4 * self.N
          )  # approximate the overall size of segment tree with array N
          self.build(1   ,    0   ,    self.N - 1			)
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_			)    ->				Optional[Any]:
          return idx * 2
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_			)    ->				Tuple:
          return idx * 2 + 1
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)    ->				str:  # noqa: E741
          if l == r:
              UpperCamelCase	:Optional[Any]     							=       A[l]
          else:
              UpperCamelCase	:List[Any]     							=       (l + r) // 2
              self.build(self.left(SCREAMING_SNAKE_CASE_			)   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)
              self.build(self.right(SCREAMING_SNAKE_CASE_			)   ,    mid + 1   ,    SCREAMING_SNAKE_CASE_			)
              UpperCamelCase	:Dict     							=       max(self.st[self.left(SCREAMING_SNAKE_CASE_			)]   ,    self.st[self.right(SCREAMING_SNAKE_CASE_			)]			)
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)    ->				Optional[Any]:
          return self.update_recursive(1   ,    0   ,    self.N - 1   ,    a - 1   ,    b - 1   ,    SCREAMING_SNAKE_CASE_			)
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)    ->				Optional[int]:  # noqa: E741
          if r < a or l > b:
              return True
          if l == r:
              UpperCamelCase	:List[Any]     							=       val
              return True
          UpperCamelCase	:Union[str, Any]     							=       (l + r) // 2
          self.update_recursive(self.left(SCREAMING_SNAKE_CASE_			)   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)
          self.update_recursive(self.right(SCREAMING_SNAKE_CASE_			)   ,    mid + 1   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)
          UpperCamelCase	:Dict     							=       max(self.st[self.left(SCREAMING_SNAKE_CASE_			)]   ,    self.st[self.right(SCREAMING_SNAKE_CASE_			)]			)
          return True
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)    ->				Dict:
          return self.query_recursive(1   ,    0   ,    self.N - 1   ,    a - 1   ,    b - 1			)
      def    UpperCAmelCase						(    self   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)    ->				Dict:  # noqa: E741
          if r < a or l > b:
              return -math.inf
          if l >= a and r <= b:
              return self.st[idx]
          UpperCamelCase	:List[Any]     							=       (l + r) // 2
          UpperCamelCase	:Union[str, Any]     							=       self.query_recursive(self.left(SCREAMING_SNAKE_CASE_			)   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)
          UpperCamelCase	:Any     							=       self.query_recursive(self.right(SCREAMING_SNAKE_CASE_			)   ,    mid + 1   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)
          return max(SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)




      def    UpperCAmelCase						(    self			)    ->				Any:
          UpperCamelCase	:Optional[int]     							=       []
          for i in range(1   ,    N + 1			):
              show_list += [self.query(SCREAMING_SNAKE_CASE_   ,    SCREAMING_SNAKE_CASE_			)]
          print(SCREAMING_SNAKE_CASE_			)


if __name__ == "__main__":
 __snake_case							 =  [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
 __snake_case							 =  15
 __snake_case							 =  SegmentTree(A)
 print(segt.query(4, 6))
 print(segt.query(7, 11))
 print(segt.query(7, 12))
 segt.update(1, 3, 1_11)
 print(segt.query(1, 15))
 segt.update(7, 8, 2_35)
 segt.show_data()













def   _A       (    SCREAMING_SNAKE_CASE__  :     int = 998001	):

    # fetches the next number
    for number in range(n - 1					,  9999					,  -1	):
        UpperCamelCase	:Union[str, Any]     							=       str(SCREAMING_SNAKE_CASE__	)

        # checks whether 'str_number' is a palindrome.
        if str_number == str_number[::-1]:
            UpperCamelCase	:Dict     							=       999

            # if 'number' is a product of two 3-digit numbers
            # then number is the answer otherwise fetch next number.
            while divisor != 99:
                if (number % divisor == 0) and (len(str(number // divisor	)	) == 3.0):
                    return number
                divisor -= 1
    raise ValueError('''That number is larger than our acceptable range.'''	)


if __name__ == "__main__":
 print(f'''{solution() = }''')





