
import math




class 	lowercase_      :


  '''simple docstring'''







  def __init__(			self      :			Optional[int]      ,							UpperCamelCase__      :			str   )      ->     List[str]:







    """simple docstring"""






    __magic_name__    					=	len(UpperCamelCase__   )
    __magic_name__    					=	[0] * (
        4 * self.N
    )  # approximate the overall size of segment tree with array N
    self.build(1      ,							0      ,							self.N - 1   )
  def 							_lowercase							(			self      :			List[Any]      ,							UpperCamelCase__      :			Optional[Any]   )      ->     Optional[int]:







    """simple docstring"""






    return idx * 2
  def 							_lowercase							(			self      :			str      ,							UpperCamelCase__      :			Tuple   )      ->     List[str]:







    """simple docstring"""






    return idx * 2 + 1
  def 							_lowercase							(			self      :			int      ,							UpperCamelCase__      :			int      ,							UpperCamelCase__      :			Tuple      ,							UpperCamelCase__      :			Dict   )      ->     str:  # noqa: E741







    """simple docstring"""






    if l == r:
      __magic_name__    					=	A[l]
    else:
      __magic_name__    					=	(l + r) // 2
      self.build(self.left(UpperCamelCase__   )      ,							UpperCamelCase__      ,							UpperCamelCase__   )
      self.build(self.right(UpperCamelCase__   )      ,							mid + 1      ,							UpperCamelCase__   )
      __magic_name__    					=	max(self.st[self.left(UpperCamelCase__   )]      ,							self.st[self.right(UpperCamelCase__   )]   )
  def 							_lowercase							(			self      :			int      ,							UpperCamelCase__      :			Tuple      ,							UpperCamelCase__      :			Any      ,							UpperCamelCase__      :			Any   )      ->     Any:







    """simple docstring"""






    return self.update_recursive(1      ,							0      ,							self.N - 1      ,							a - 1      ,							b - 1      ,							UpperCamelCase__   )
  def 							_lowercase							(			self      :			Any      ,							UpperCamelCase__      :			Dict      ,							UpperCamelCase__      :			Dict      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			Optional[int]      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			Optional[Any]   )      ->     str:  # noqa: E741







    """simple docstring"""






    if r < a or l > b:
      return True
    if l == r:
      __magic_name__    					=	val
      return True
    __magic_name__    					=	(l + r) // 2
    self.update_recursive(self.left(UpperCamelCase__   )      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    self.update_recursive(self.right(UpperCamelCase__   )      ,							mid + 1      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    __magic_name__    					=	max(self.st[self.left(UpperCamelCase__   )]      ,							self.st[self.right(UpperCamelCase__   )]   )
    return True
  def 							_lowercase							(			self      :			List[str]      ,							UpperCamelCase__      :			List[str]      ,							UpperCamelCase__      :			Optional[int]   )      ->     Union[str, Any]:







    """simple docstring"""






    return self.query_recursive(1      ,							0      ,							self.N - 1      ,							a - 1      ,							b - 1   )
  def 							_lowercase							(			self      :			Union[str, Any]      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			str      ,							UpperCamelCase__      :			Tuple      ,							UpperCamelCase__      :			Optional[Any]      ,							UpperCamelCase__      :			Union[str, Any]   )      ->     Any:  # noqa: E741







    """simple docstring"""






    if r < a or l > b:
      return -math.inf
    if l >= a and r <= b:
      return self.st[idx]
    __magic_name__    					=	(l + r) // 2
    __magic_name__    					=	self.query_recursive(self.left(UpperCamelCase__   )      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    __magic_name__    					=	self.query_recursive(self.right(UpperCamelCase__   )      ,							mid + 1      ,							UpperCamelCase__      ,							UpperCamelCase__      ,							UpperCamelCase__   )
    return max(UpperCamelCase__      ,							UpperCamelCase__   )





  def 							_lowercase							(			self      :			int   )      ->     int:







    """simple docstring"""






    __magic_name__    					=	[]
    for i in range(1      ,							N + 1   ):
      show_list += [self.query(UpperCamelCase__      ,							UpperCamelCase__   )]
    print(UpperCamelCase__   )


if __name__ == "__main__":
    __lowerCAmelCase      :					int   	=       [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
    __lowerCAmelCase      :					Optional[Any]   	=       15
    __lowerCAmelCase      :					Tuple   	=       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()



def a__   (	A_ ):






  '''simple docstring'''





  __magic_name__    					=	str(A_ ).strip()
  if not bin_string:
    raise ValueError("""Empty string was passed to the function""" )
  __magic_name__    					=	bin_string[0] == """-"""
  if is_negative:
    __magic_name__    					=	bin_string[1:]
  if not all(char in """01""" for char in bin_string ):
    raise ValueError("""Non-binary value was passed to the function""" )
  __magic_name__    					=	0
  for char in bin_string:
    __magic_name__    					=	2 * decimal_number + int(A_ )
  return -decimal_number if is_negative else decimal_number


if __name__ == "__main__":
    from doctest import testmod

    testmod()

