






'''simple docstring'''
from collections.abc import Sequence
from queue import Queue


class        _UpperCAmelCase						:




    def __init__(			self  :       List[Any]  ,     a  :       List[Any]  ,     a  :       List[Any]  ,     a  :       int  ,     a  :       Optional[Any]=None  ,     a  :       Optional[int]=None			):






       '''simple docstring'''






       lowercase_	:    Dict           =     start
       lowercase_	:    Tuple           =     end
       lowercase_	:    Any           =     val
       lowercase_	:    Optional[int]           =     (start + end) // 2
       lowercase_	:    Any           =     left
       lowercase_	:    List[str]           =     right





    def __repr__(			self  :       Union[str, Any]			):






       '''simple docstring'''






       return f"""SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})"""


class        _UpperCAmelCase						:




    def __init__(			self  :       Union[str, Any]  ,     a  :       Sequence  ,     a  :       Optional[int]			):






       '''simple docstring'''






       lowercase_	:    List[str]           =     collection
       lowercase_	:    Union[str, Any]           =     function
       if self.collection:
          lowercase_	:    Union[str, Any]           =     self._build_tree(0  ,     len(a			) - 1			)




    def 				lowerCAmelCase__				(			self  :       str  ,     a  :       Optional[int]  ,     a  :       List[Any]			):






       '''simple docstring'''






       self._update_tree(self.root  ,     a  ,     a			)




    def 				lowerCAmelCase__				(			self  :       List[Any]  ,     a  :       Tuple  ,     a  :       Dict			):






       '''simple docstring'''






       return self._query_range(self.root  ,     a  ,     a			)




    def 				lowerCAmelCase__				(			self  :       List[str]  ,     a  :       List[str]  ,     a  :       Tuple			):






       '''simple docstring'''






       if start == end:
          return SegmentTreeNode(a  ,     a  ,     self.collection[start]			)
       lowercase_	:    Union[str, Any]           =     (start + end) // 2
       lowercase_	:    Dict           =     self._build_tree(a  ,     a			)
       lowercase_	:    Union[str, Any]           =     self._build_tree(mid + 1  ,     a			)
       return SegmentTreeNode(a  ,     a  ,     self.fn(left.val  ,     right.val			)  ,     a  ,     a			)




    def 				lowerCAmelCase__				(			self  :       Union[str, Any]  ,     a  :       Dict  ,     a  :       Tuple  ,     a  :       List[str]			):






       '''simple docstring'''






       if node.start == i and node.end == i:
          lowercase_	:    Union[str, Any]           =     val
          return
       if i <= node.mid:
          self._update_tree(node.left  ,     a  ,     a			)
       else:
          self._update_tree(node.right  ,     a  ,     a			)
       lowercase_	:    int           =     self.fn(node.left.val  ,     node.right.val			)




    def 				lowerCAmelCase__				(			self  :       Optional[Any]  ,     a  :       Union[str, Any]  ,     a  :       Any  ,     a  :       List[Any]			):






       '''simple docstring'''






       if node.start == i and node.end == j:
          return node.val

       if i <= node.mid:
          if j <= node.mid:
             # range in left child tree
             return self._query_range(node.left  ,     a  ,     a			)
          else:
             # range in left child tree and right child tree
             return self.fn(
                 self._query_range(node.left  ,     a  ,     node.mid			)  ,     self._query_range(node.right  ,     node.mid + 1  ,     a			)  ,     )
       else:
          # range in right child tree
          return self._query_range(node.right  ,     a  ,     a			)





    def 				lowerCAmelCase__				(			self  :       int			):






       '''simple docstring'''






       if self.root is not None:
          lowercase_	:    List[str]           =     Queue()
          queue.put(self.root			)
          while not queue.empty():
             lowercase_	:    List[Any]           =     queue.get()
             yield node

             if node.left is not None:
                queue.put(node.left			)

             if node.right is not None:
                queue.put(node.right			)


if __name__ == "__main__":
 import operator

 for fn in [operator.add, max, min]:
  print('*' * 50)
  UpperCamelCase__ =			SegmentTree([2, 1, 5, 3, 4], fn)
  for node in arr.traverse():
   print(node)
  print()

  arr.update(1, 5)
  for node in arr.traverse():
   print(node)
  print()

  print(arr.query_range(3, 4))  # 7
  print(arr.query_range(2, 2))  # 5
  print(arr.query_range(1, 3))  # 13
  print()












'''simple docstring'''
def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase = 200							):


   """simple docstring"""




   lowercase_	:    Optional[int]           =     [1, 2, 5, 10, 20, 50, 100, 200]
   lowercase_	:    str           =     [0] * (pence + 1)
   lowercase_	:    Dict           =     1  # base case: 1 way to make 0 pence

   for coin in coins:
      for i in range(_UpperCamelCase						,		pence + 1						,		1							):
         number_of_ways[i] += number_of_ways[i - coin]
   return number_of_ways[pence]


if __name__ == "__main__":
 assert solution(200) == 73682




