
"""simple docstring"""




lowerCAmelCase__							=				'''ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'''



def        _lowerCamelCase ( __a    ):

		if not isinstance(UpperCAmelCase__,							UpperCAmelCase__    ):
				SCREAMING_SNAKE_CASE_						 = F'a bytes-like object is required, not \'{data.__class__.__name__}\''
				raise TypeError(UpperCAmelCase__    )

		SCREAMING_SNAKE_CASE_						 = ''''''.join(bin(UpperCAmelCase__    )[2:].zfill(8    ) for byte in data    )

		SCREAMING_SNAKE_CASE_						 = len(UpperCAmelCase__    ) % 6 != 0

		if padding_needed:
				# The padding that will be added later
				SCREAMING_SNAKE_CASE_						 = B'''=''' * ((6 - len(UpperCAmelCase__    ) % 6) // 2)

				# Append binary_stream with arbitrary binary digits (0's by default) to make its
				# length a multiple of 6.
				binary_stream += "0" * (6 - len(UpperCAmelCase__    ) % 6)
		else:
				SCREAMING_SNAKE_CASE_						 = B''''''

		# Encode every 6 binary digits to their corresponding Base64 character
		return (
		    "".join(
		        B64_CHARSET[int(binary_stream[index : index + 6],							2    )]
		        for index in range(0,							len(UpperCAmelCase__    ),							6    )    ).encode()
		    + padding
		)



def        _lowerCamelCase ( __a    ):

		if not isinstance(UpperCAmelCase__,							UpperCAmelCase__    ) and not isinstance(UpperCAmelCase__,							UpperCAmelCase__    ):
				SCREAMING_SNAKE_CASE_						 = (
				    '''argument should be a bytes-like object or ASCII string, '''
				    F'not \'{encoded_data.__class__.__name__}\''
				)
				raise TypeError(UpperCAmelCase__    )

		# In case encoded_data is a bytes-like object, make sure it contains only
		# ASCII characters so we convert it to a string object
		if isinstance(UpperCAmelCase__,							UpperCAmelCase__    ):
				try:
						SCREAMING_SNAKE_CASE_						 = encoded_data.decode('''utf-8'''    )
				except UnicodeDecodeError:
						raise ValueError('''base64 encoded data should only contain ASCII characters'''    )

		SCREAMING_SNAKE_CASE_						 = encoded_data.count('''='''    )

		# Check if the encoded string contains non base64 characters
		if padding:
				assert all(
				    char in B64_CHARSET for char in encoded_data[:-padding]    ), "Invalid base64 character(s) found."
		else:
				assert all(
				    char in B64_CHARSET for char in encoded_data    ), "Invalid base64 character(s) found."

		# Check the padding
		assert len(UpperCAmelCase__    ) % 4 == 0 and padding < 3, "Incorrect padding"

		if padding:
				# Remove padding if there is one
				SCREAMING_SNAKE_CASE_						 = encoded_data[:-padding]

				SCREAMING_SNAKE_CASE_						 = ''''''.join(
				    bin(B64_CHARSET.index(UpperCAmelCase__    )    )[2:].zfill(6    ) for char in encoded_data    )[: -padding * 2]
		else:
				SCREAMING_SNAKE_CASE_						 = ''''''.join(
				    bin(B64_CHARSET.index(UpperCAmelCase__    )    )[2:].zfill(6    ) for char in encoded_data    )

		SCREAMING_SNAKE_CASE_						 = [
		    int(binary_stream[index : index + 8],							2    )
		    for index in range(0,							len(UpperCAmelCase__    ),							8    )
		]

		return bytes(UpperCAmelCase__    )


if __name__ == "__main__":
						import doctest

						doctest.testmod()

"""simple docstring"""




from collections.abc import Sequence
from queue import Queue





class  snake_case     :

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

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = start
									SCREAMING_SNAKE_CASE_						 = end
									SCREAMING_SNAKE_CASE_						 = val
									SCREAMING_SNAKE_CASE_						 = (start + end) // 2
									SCREAMING_SNAKE_CASE_						 = left
									SCREAMING_SNAKE_CASE_						 = right







							def __repr__(self    ):

									"""simple docstring"""







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







class  snake_case     :

							def __init__(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									SCREAMING_SNAKE_CASE_						 = collection
									SCREAMING_SNAKE_CASE_						 = function
									if self.collection:
											SCREAMING_SNAKE_CASE_						 = self._build_tree(0       ,       len(SCREAMING_SNAKE_CASE_    ) - 1    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									self._update_tree(self.root       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







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

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									if start == end:
											return SegmentTreeNode(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       self.collection[start]    )
									SCREAMING_SNAKE_CASE_						 = (start + end) // 2
									SCREAMING_SNAKE_CASE_						 = self._build_tree(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									SCREAMING_SNAKE_CASE_						 = self._build_tree(mid + 1       ,       SCREAMING_SNAKE_CASE_    )
									return SegmentTreeNode(SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       self.fn(left.val       ,       right.val    )       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""simple docstring"""







									if node.start == i and node.end == i:
											SCREAMING_SNAKE_CASE_						 = val
											return
									if i <= node.mid:
											self._update_tree(node.left       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									else:
											self._update_tree(node.right       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
									SCREAMING_SNAKE_CASE_						 = self.fn(node.left.val       ,       node.right.val    )

							def _lowercase					(self       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    ):

									"""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       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )
											else:
													# range in left child tree and right child tree
													return self.fn(
													    self._query_range(node.left       ,       SCREAMING_SNAKE_CASE_       ,       node.mid    )       ,       self._query_range(node.right       ,       node.mid + 1       ,       SCREAMING_SNAKE_CASE_    )       ,       )
									else:
											# range in right child tree
											return self._query_range(node.right       ,       SCREAMING_SNAKE_CASE_       ,       SCREAMING_SNAKE_CASE_    )







							def _lowercase					(self    ):

									"""simple docstring"""







									if self.root is not None:
											SCREAMING_SNAKE_CASE_						 = Queue()
											queue.put(self.root    )
											while not queue.empty():
													SCREAMING_SNAKE_CASE_						 = 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()