


from collections.abc import Sequence
from queue import Queue


class   snake_case_ :




       """simple docstring"""






       def __init__(     self     ,lowercase     ,lowercase     ,lowercase     ,lowercase=None     ,lowercase=None):

             """simple docstring"""





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



       def __repr__(     self):

             """simple docstring"""





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


class   snake_case_ :




       """simple docstring"""






       def __init__(     self     ,lowercase     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	Optional[int]				      =		collection
             UpperCAmelCase_  :	str				      =		function
             if self.collection:
                   UpperCAmelCase_  :	Optional[Any]				      =		self._build_tree(0     ,len(__a) - 1)



       def  A_   (     self     ,lowercase     ,lowercase):

             """simple docstring"""





             self._update_tree(self.root     ,__a     ,__a)



       def  A_   (     self     ,lowercase     ,lowercase):

             """simple docstring"""





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



       def  A_   (     self     ,lowercase     ,lowercase):

             """simple docstring"""





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



       def  A_   (     self     ,lowercase     ,lowercase     ,lowercase):

             """simple docstring"""





             if node.start == i and node.end == i:
                   UpperCAmelCase_  :	Optional[Any]				      =		val
                   return
             if i <= node.mid:
                   self._update_tree(node.left     ,__a     ,__a)
             else:
                   self._update_tree(node.right     ,__a     ,__a)
             UpperCAmelCase_  :	Optional[int]				      =		self.fn(node.left.val     ,node.right.val)



       def  A_   (     self     ,lowercase     ,lowercase     ,lowercase):

             """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  A_   (     self):

             """simple docstring"""





             if self.root is not None:
                   UpperCAmelCase_  :	Union[str, Any]				      =		Queue()
                   queue.put(self.root)
                   while not queue.empty():
                         UpperCAmelCase_  :	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)
      __lowerCamelCase         =			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()





def    _snake_case (       __snake_case					,  __snake_case    )     ->     str:






      '''simple docstring'''







      if a < 0 or b < 0:
            raise ValueError("the value of both inputs must be positive"    )

      UpperCAmelCase_  :	List[Any]				      =		str(bin(__snake_case    )    )[2:]  # remove the leading "0b"
      UpperCAmelCase_  :	int				      =		str(bin(__snake_case    )    )[2:]  # remove the leading "0b"

      UpperCAmelCase_  :	Optional[int]				      =		max(len(__snake_case    )					,  len(__snake_case    )    )

      return "0b" + "".join(
          str(int(char_a == "1" and char_b == "1"    )    )
          for char_a, char_b in zip(a_binary.zfill(__snake_case    )					,  b_binary.zfill(__snake_case    )    )    )


if __name__ == "__main__":
   import doctest

   doctest.testmod()
