

from __future__ import annotations

import math






class 	__magic_name__    :





			def __init__(		self					,  __snake_case					)   -> None:




						'''simple docstring'''
						__a        =size
						# approximate the overall size of segment tree with given value
						__a        =[0 for i in range(0					,  4 * size					)]
						# create array to store lazy update
						__a        =[0 for i in range(0					,  4 * size					)]
						__a        =[0 for i in range(0					,  4 * size					)]  # flag for lazy update





			def 		__magic_name__    (		self					,  __snake_case					)   -> int:




						'''simple docstring'''
						return idx * 2





			def 		__magic_name__    (		self					,  __snake_case					)   -> int:




						'''simple docstring'''
						return idx * 2 + 1





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					)   -> None:




						'''simple docstring'''
						if left_element == right_element:
									__a        =a[left_element - 1]
						else:
									__a        =(left_element + right_element) // 2
									self.build(self.left(__snake_case					)					,  __snake_case					,  __snake_case					,  __snake_case					)
									self.build(self.right(__snake_case					)					,  mid + 1					,  __snake_case					,  __snake_case					)
									__a        =max(
									    self.segment_tree[self.left(__snake_case					)]					,  self.segment_tree[self.right(__snake_case					)]					)





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					)   -> bool:




						'''simple docstring'''
						if self.flag[idx] is True:
									__a        =self.lazy[idx]
									__a        =False
									if left_element != right_element:
												__a        =self.lazy[idx]
												__a        =self.lazy[idx]
												__a        =True
												__a        =True

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





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					)   -> int | float:




						'''simple docstring'''
						if self.flag[idx] is True:
									__a        =self.lazy[idx]
									__a        =False
									if left_element != right_element:
												__a        =self.lazy[idx]
												__a        =self.lazy[idx]
												__a        =True
												__a        =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]
						__a        =(left_element + right_element) // 2
						__a        =self.query(self.left(__snake_case					)					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					)
						__a        =self.query(self.right(__snake_case					)					,  mid + 1					,  __snake_case					,  __snake_case					,  __snake_case					)
						return max(__snake_case					,  __snake_case					)





			def __str__(		self					)   -> str:




						'''simple docstring'''
						return str([self.query(1					,  1					,  self.size					,  __snake_case					,  __snake_case					) for i in range(1					,  self.size + 1					)]					)


if __name__ == "__main__":
						_lowerCAmelCase					:			str  				=			[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
						_lowerCAmelCase					:			Optional[Any]  				=			15
						_lowerCAmelCase					:			Tuple  				=			SegmentTree(size)
						segt.build(1, 1, size, A)
						print(segt.query(1, 1, size, 4, 6))
						print(segt.query(1, 1, size, 7, 11))
						print(segt.query(1, 1, size, 7, 12))
						segt.update(1, 1, size, 1, 3, 111)
						print(segt.query(1, 1, size, 1, 15))
						segt.update(1, 1, size, 7, 8, 235)
						print(segt)









_lowerCAmelCase					:			Optional[int]  				=			"\n# Transformers installation\n! pip install transformers datasets\n# To install from source instead of the last release, comment the command above and uncomment the following one.\n# ! pip install git+https://github.com/huggingface/transformers.git\n"

_lowerCAmelCase					:			Tuple  				=			[{"type": "code", "content": INSTALL_CONTENT}]
_lowerCAmelCase					:			Optional[int]  				=			{
    "{processor_class}": "FakeProcessorClass",
    "{model_class}": "FakeModelClass",
    "{object_class}": "FakeObjectClass",
}






