




'''simple docstring'''







import math


class      _a    :
       def __init__(      self		:      List[Any]  ,							lowercase		:      str							):



           '''simple docstring'''

           UpperCAmelCase     			=						len(lowercase							)
           UpperCAmelCase     			=						[0] * (
               4 * self.N
           )  # approximate the overall size of segment tree with array N
           self.build(1  ,							0  ,							self.N - 1							)
       def        A (      self		:      List[Any]  ,							lowercase		:      List[Any]							):



           '''simple docstring'''

           return idx * 2
       def        A (      self		:      str  ,							lowercase		:      Any							):



           '''simple docstring'''

           return idx * 2 + 1
       def        A (      self		:      Any  ,							lowercase		:      Any  ,							lowercase		:      Union[str, Any]  ,							lowercase		:      Optional[Any]							):  # noqa: E741



           '''simple docstring'''

           if l == r:
               UpperCAmelCase     			=						A[l]
           else:
               UpperCAmelCase     			=						(l + r) // 2
               self.build(self.left(lowercase							)  ,							lowercase  ,							lowercase							)
               self.build(self.right(lowercase							)  ,							mid + 1  ,							lowercase							)
               UpperCAmelCase     			=						max(self.st[self.left(lowercase							)]  ,							self.st[self.right(lowercase							)]							)
       def        A (      self		:      List[Any]  ,							lowercase		:      Optional[int]  ,							lowercase		:      Any  ,							lowercase		:      Dict							):



           '''simple docstring'''

           return self.update_recursive(1  ,							0  ,							self.N - 1  ,							a - 1  ,							b - 1  ,							lowercase							)
       def        A (      self		:      List[Any]  ,							lowercase		:      str  ,							lowercase		:      int  ,							lowercase		:      List[Any]  ,							lowercase		:      int  ,							lowercase		:      str  ,							lowercase		:      List[str]							):  # noqa: E741



           '''simple docstring'''

           if r < a or l > b:
               return True
           if l == r:
               UpperCAmelCase     			=						val
               return True
           UpperCAmelCase     			=						(l + r) // 2
           self.update_recursive(self.left(lowercase							)  ,							lowercase  ,							lowercase  ,							lowercase  ,							lowercase  ,							lowercase							)
           self.update_recursive(self.right(lowercase							)  ,							mid + 1  ,							lowercase  ,							lowercase  ,							lowercase  ,							lowercase							)
           UpperCAmelCase     			=						max(self.st[self.left(lowercase							)]  ,							self.st[self.right(lowercase							)]							)
           return True
       def        A (      self		:      Tuple  ,							lowercase		:      Dict  ,							lowercase		:      Optional[Any]							):



           '''simple docstring'''

           return self.query_recursive(1  ,							0  ,							self.N - 1  ,							a - 1  ,							b - 1							)
       def        A (      self		:      List[Any]  ,							lowercase		:      str  ,							lowercase		:      Any  ,							lowercase		:      int  ,							lowercase		:      int  ,							lowercase		:      Dict							):  # noqa: E741



           '''simple docstring'''

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







       def        A (      self		:      Optional[int]							):



           '''simple docstring'''

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


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










'''simple docstring'''







def 		snake_case_				(_a      :				Any       ,  _a      :				Union[str, Any]	):
    if n < 0:
        return 0
    # table[i] represents the number of ways to get to amount i
    UpperCAmelCase     			=						[0] * (n + 1)

    # There is exactly 1 way to get to zero(You pick no coins).
    UpperCAmelCase     			=						1

    # Pick all coins one by one and update table[] values
    # after the index greater than or equal to the value of the
    # picked coin
    for coin_val in s:
        for j in range(_a       ,  n + 1	):
            table[j] += table[j - coin_val]

    return table[n]


if __name__ == "__main__":
   import doctest

   doctest.testmod()




