






"""simple docstring"""



from __future__ import annotations

import math

class        a     :







    def __init__(			self							,		_lowerCamelCase       ):
      lowercase							    =       size
      # approximate the overall size of segment tree with given value
      lowercase							    =       [0 for i in range(0							,		4 * size       )]
      # create array to store lazy update
      lowercase							    =       [0 for i in range(0							,		4 * size       )]
      lowercase							    =       [0 for i in range(0							,		4 * size       )]  # flag for lazy update







    def 			UpperCamelCase_      (			self							,		_lowerCamelCase       ):
      return idx * 2







    def 			UpperCamelCase_      (			self							,		_lowerCamelCase       ):
      return idx * 2 + 1







    def 			UpperCamelCase_      (			self							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       ):
      if left_element == right_element:
        lowercase							    =       a[left_element - 1]
      else:
        lowercase							    =       (left_element + right_element) // 2
        self.build(self.left(_lowerCamelCase       )							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       )
        self.build(self.right(_lowerCamelCase       )							,		mid + 1							,		_lowerCamelCase							,		_lowerCamelCase       )
        lowercase							    =       max(
            self.segment_tree[self.left(_lowerCamelCase       )]							,		self.segment_tree[self.right(_lowerCamelCase       )]       )







    def 			UpperCamelCase_      (			self							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       ):
      if self.flag[idx] is True:
        lowercase							    =       self.lazy[idx]
        lowercase							    =       False
        if left_element != right_element:
          lowercase							    =       self.lazy[idx]
          lowercase							    =       self.lazy[idx]
          lowercase							    =       True
          lowercase							    =       True

      if right_element < a or left_element > b:
        return True
      if left_element >= a and right_element <= b:
        lowercase							    =       val
        if left_element != right_element:
          lowercase							    =       val
          lowercase							    =       val
          lowercase							    =       True
          lowercase							    =       True
        return True
      lowercase							    =       (left_element + right_element) // 2
      self.update(self.left(_lowerCamelCase       )							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       )
      self.update(self.right(_lowerCamelCase       )							,		mid + 1							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       )
      lowercase							    =       max(
          self.segment_tree[self.left(_lowerCamelCase       )]							,		self.segment_tree[self.right(_lowerCamelCase       )]       )
      return True







    def 			UpperCamelCase_      (			self							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       ):
      if self.flag[idx] is True:
        lowercase							    =       self.lazy[idx]
        lowercase							    =       False
        if left_element != right_element:
          lowercase							    =       self.lazy[idx]
          lowercase							    =       self.lazy[idx]
          lowercase							    =       True
          lowercase							    =       True
      if right_element < a or left_element > b:
        return -math.inf
      if left_element >= a and right_element <= b:
        return self.segment_tree[idx]
      lowercase							    =       (left_element + right_element) // 2
      lowercase							    =       self.query(self.left(_lowerCamelCase       )							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       )
      lowercase							    =       self.query(self.right(_lowerCamelCase       )							,		mid + 1							,		_lowerCamelCase							,		_lowerCamelCase							,		_lowerCamelCase       )
      return max(_lowerCamelCase							,		_lowerCamelCase       )







    def __str__(			self       ):
      return str([self.query(1							,		1							,		self.size							,		_lowerCamelCase							,		_lowerCamelCase       ) for i in range(1							,		self.size + 1       )]       )


if __name__ == "__main__":
    _UpperCamelCase		:  List[str]						=		[1, 2, -4, 7, 3, -5, 6, 1_1, -2_0, 9, 1_4, 1_5, 5, 2, -8]
    _UpperCamelCase		:  Dict						=		1_5
    _UpperCamelCase		:  Any						=		SegmentTree(size)
    segt.build(1, 1, size, A)
    print(segt.query(1, 1, size, 4, 6))
    print(segt.query(1, 1, size, 7, 1_1))
    print(segt.query(1, 1, size, 7, 1_2))
    segt.update(1, 1, size, 1, 3, 1_1_1)
    print(segt.query(1, 1, size, 1, 1_5))
    segt.update(1, 1, size, 7, 8, 2_3_5)
    print(segt)










"""simple docstring"""



def 						_SCREAMING_SNAKE_CASE (    __snake_case			:  int = 1_00    ):





  '''simple docstring'''





  lowercase							    =       0
  lowercase							    =       0
  for i in range(1		,					n + 1    ):
    sum_of_squares += i**2
    sum_of_ints += i
  return sum_of_ints**2 - sum_of_squares


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


