




import math






class       A      :
     """simple docstring"""

     def __init__(     self	: List[str]						,	A__	: List[str]      )					->							int:
           lowerCamelCase__   	=					len(A__      )
           lowerCamelCase__   	=					[0] * (
               4 * self.N
           )  # approximate the overall size of segment tree with array N
           self.build(1						,	0						,	self.N - 1      )




     def 			__snake_case (     self	: Any						,	A__	: str      )					->							Any:
           return idx * 2




     def 			__snake_case (     self	: str						,	A__	: Dict      )					->							List[str]:
           return idx * 2 + 1




     def 			__snake_case (     self	: Any						,	A__	: Tuple						,	A__	: Optional[Any]						,	A__	: Union[str, Any]      )					->							str:  # noqa: E741
           if l == r:
                 lowerCamelCase__   	=					A[l]
           else:
                 lowerCamelCase__   	=					(l + r) // 2
                 self.build(self.left(A__      )						,	A__						,	A__      )
                 self.build(self.right(A__      )						,	mid + 1						,	A__      )
                 lowerCamelCase__   	=					max(self.st[self.left(A__      )]						,	self.st[self.right(A__      )]      )




     def 			__snake_case (     self	: List[str]						,	A__	: Any						,	A__	: List[Any]						,	A__	: str      )					->							Union[str, Any]:
           return self.update_recursive(1						,	0						,	self.N - 1						,	a - 1						,	b - 1						,	A__      )




     def 			__snake_case (     self	: Optional[Any]						,	A__	: Tuple						,	A__	: Dict						,	A__	: List[Any]						,	A__	: Dict						,	A__	: List[str]						,	A__	: Tuple      )					->							Union[str, Any]:  # noqa: E741
           if r < a or l > b:
                 return True
           if l == r:
                 lowerCamelCase__   	=					val
                 return True
           lowerCamelCase__   	=					(l + r) // 2
           self.update_recursive(self.left(A__      )						,	A__						,	A__						,	A__						,	A__						,	A__      )
           self.update_recursive(self.right(A__      )						,	mid + 1						,	A__						,	A__						,	A__						,	A__      )
           lowerCamelCase__   	=					max(self.st[self.left(A__      )]						,	self.st[self.right(A__      )]      )
           return True




     def 			__snake_case (     self	: str						,	A__	: Optional[Any]						,	A__	: Optional[Any]      )					->							int:
           return self.query_recursive(1						,	0						,	self.N - 1						,	a - 1						,	b - 1      )




     def 			__snake_case (     self	: List[Any]						,	A__	: Any						,	A__	: Optional[int]						,	A__	: Tuple						,	A__	: List[str]						,	A__	: List[str]      )					->							str:  # noqa: E741
           if r < a or l > b:
                 return -math.inf
           if l >= a and r <= b:
                 return self.st[idx]
           lowerCamelCase__   	=					(l + r) // 2
           lowerCamelCase__   	=					self.query_recursive(self.left(A__      )						,	A__						,	A__						,	A__						,	A__      )
           lowerCamelCase__   	=					self.query_recursive(self.right(A__      )						,	mid + 1						,	A__						,	A__						,	A__      )
           return max(A__						,	A__      )




     def 			__snake_case (     self	: List[str]      )					->							List[Any]:
           lowerCamelCase__   	=					[]
           for i in range(1						,	N + 1      ):
                 show_list += [self.query(A__						,	A__      )]
           print(A__      )


if __name__ == "__main__":
      __SCREAMING_SNAKE_CASE     : Dict      =[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
      __SCREAMING_SNAKE_CASE     : Any      =15
      __SCREAMING_SNAKE_CASE     : List[Any]      =SegmentTree(A)
      print(segt.query(4, 6))
      print(segt.query(7, 11))
      print(segt.query(7, 12))
      segt.update(1, 3, 111)
      print(segt.query(1, 15))
      segt.update(7, 8, 235)
      segt.show_data()





import math

def       lowerCAmelCase_      (	lowerCamelCase:							int    )       ->      str:


      '''simple docstring'''




      if number == 0:
            lowerCamelCase__   	=					'Zero'
            return words
      else:
            lowerCamelCase__   	=					math.logaa(lowerCamelCase    )
            lowerCamelCase__   	=					digits + 1
            lowerCamelCase__   	=					{}
            lowerCamelCase__   	=					''
            lowerCamelCase__   	=					'One'
            lowerCamelCase__   	=					'Two'
            lowerCamelCase__   	=					'Three'
            lowerCamelCase__   	=					'Four'
            lowerCamelCase__   	=					'Five'
            lowerCamelCase__   	=					'Six'
            lowerCamelCase__   	=					'Seven'
            lowerCamelCase__   	=					'Eight'
            lowerCamelCase__   	=					'Nine'

            lowerCamelCase__   	=					{}
            lowerCamelCase__   	=					''
            lowerCamelCase__   	=					'Twenty'
            lowerCamelCase__   	=					'Thirty'
            lowerCamelCase__   	=					'Forty'
            lowerCamelCase__   	=					'Fifty'
            lowerCamelCase__   	=					'Sixty'
            lowerCamelCase__   	=					'Seventy'
            lowerCamelCase__   	=					'Eighty'
            lowerCamelCase__   	=					'Ninety'

            lowerCamelCase__   	=					{}
            lowerCamelCase__   	=					'Ten'
            lowerCamelCase__   	=					'Eleven'
            lowerCamelCase__   	=					'Twelve'
            lowerCamelCase__   	=					'Thirteen'
            lowerCamelCase__   	=					'Fourteen'
            lowerCamelCase__   	=					'Fifteen'
            lowerCamelCase__   	=					'Sixteen'
            lowerCamelCase__   	=					'Seventeen'
            lowerCamelCase__   	=					'Eighteen'
            lowerCamelCase__   	=					'Nineteen'

            lowerCamelCase__   	=					{}
            lowerCamelCase__   	=					'Hundred,'
            lowerCamelCase__   	=					'Thousand,'
            lowerCamelCase__   	=					'Lakh,'
            lowerCamelCase__   	=					'Crore,'

            lowerCamelCase__   	=					number
            lowerCamelCase__   	=					''
            lowerCamelCase__   	=					0
            lowerCamelCase__   	=					int(lowerCamelCase    )
            while counter < digits:
                  lowerCamelCase__   	=					temp_num % 10
                  if counter % 2 == 0:
                        lowerCamelCase__   	=					''
                        if counter in placevalue and current != 0:
                              lowerCamelCase__   	=					placevalue[counter]
                        if counter == 2:
                              lowerCamelCase__   	=					singles[current] + addition + words
                        elif counter == 0:
                              if ((temp_num % 1_00) // 10) == 1:
                                    lowerCamelCase__   	=					teens[current] + addition + words
                                    lowerCamelCase__   	=					temp_num // 10
                                    counter += 1
                              else:
                                    lowerCamelCase__   	=					singles[current] + addition + words

                        else:
                              lowerCamelCase__   	=					doubles[current] + addition + words

                  else:
                        if counter == 1:
                              if current == 1:
                                    lowerCamelCase__   	=					teens[number % 10] + words
                              else:
                                    lowerCamelCase__   	=					''
                                    if counter in placevalue:
                                          lowerCamelCase__   	=					placevalue[counter]
                                    lowerCamelCase__   	=					doubles[current] + addition + words
                        else:
                              lowerCamelCase__   	=					''
                              if counter in placevalue:
                                    if current == 0 and ((temp_num % 1_00) // 10) == 0:
                                          lowerCamelCase__   	=					''
                                    else:
                                          lowerCamelCase__   	=					placevalue[counter]
                              if ((temp_num % 1_00) // 10) == 1:
                                    lowerCamelCase__   	=					teens[current] + addition + words
                                    lowerCamelCase__   	=					temp_num // 10
                                    counter += 1
                              else:
                                    lowerCamelCase__   	=					singles[current] + addition + words
                  counter += 1
                  lowerCamelCase__   	=					temp_num // 10
      return words


if __name__ == "__main__":
      import doctest

      doctest.testmod()