

import math




class 					UpperCamelCase	:




					def __init__( self :					List[Any]      ,_lowerCAmelCase :					List[str]						):


							"""simple docstring"""




							__snake_case		       =     len(_lowerCAmelCase						)
							__snake_case		       =     [0] * (
							    4 * self.N
							)  # approximate the overall size of segment tree with array N
							self.build(1      ,0      ,self.N - 1						)




					def 							UpperCamelCase_						( self :					Dict      ,_lowerCAmelCase :					Optional[Any]						):


							"""simple docstring"""




							return idx * 2




					def 							UpperCamelCase_						( self :					Optional[Any]      ,_lowerCAmelCase :					Optional[Any]						):


							"""simple docstring"""




							return idx * 2 + 1




					def 							UpperCamelCase_						( self :					Optional[Any]      ,_lowerCAmelCase :					int      ,_lowerCAmelCase :					Dict      ,_lowerCAmelCase :					List[str]						):  # noqa: E741


							"""simple docstring"""




							if l == r:
									__snake_case		       =     A[l]
							else:
									__snake_case		       =     (l + r) // 2
									self.build(self.left(_lowerCAmelCase						)      ,_lowerCAmelCase      ,_lowerCAmelCase						)
									self.build(self.right(_lowerCAmelCase						)      ,mid + 1      ,_lowerCAmelCase						)
									__snake_case		       =     max(self.st[self.left(_lowerCAmelCase						)]      ,self.st[self.right(_lowerCAmelCase						)]						)




					def 							UpperCamelCase_						( self :					int      ,_lowerCAmelCase :					int      ,_lowerCAmelCase :					List[str]      ,_lowerCAmelCase :					Union[str, Any]						):


							"""simple docstring"""




							return self.update_recursive(1      ,0      ,self.N - 1      ,a - 1      ,b - 1      ,_lowerCAmelCase						)




					def 							UpperCamelCase_						( self :					Any      ,_lowerCAmelCase :					str      ,_lowerCAmelCase :					str      ,_lowerCAmelCase :					Tuple      ,_lowerCAmelCase :					List[str]      ,_lowerCAmelCase :					Dict      ,_lowerCAmelCase :					Any						):  # noqa: E741


							"""simple docstring"""




							if r < a or l > b:
									return True
							if l == r:
									__snake_case		       =     val
									return True
							__snake_case		       =     (l + r) // 2
							self.update_recursive(self.left(_lowerCAmelCase						)      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase						)
							self.update_recursive(self.right(_lowerCAmelCase						)      ,mid + 1      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase      ,_lowerCAmelCase						)
							__snake_case		       =     max(self.st[self.left(_lowerCAmelCase						)]      ,self.st[self.right(_lowerCAmelCase						)]						)
							return True




					def 							UpperCamelCase_						( self :					List[str]      ,_lowerCAmelCase :					Tuple      ,_lowerCAmelCase :					int						):


							"""simple docstring"""




							return self.query_recursive(1      ,0      ,self.N - 1      ,a - 1      ,b - 1						)




					def 							UpperCamelCase_						( self :					int      ,_lowerCAmelCase :					List[Any]      ,_lowerCAmelCase :					Any      ,_lowerCAmelCase :					Dict      ,_lowerCAmelCase :					str      ,_lowerCAmelCase :					Tuple						):  # noqa: E741


							"""simple docstring"""




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







					def 							UpperCamelCase_						( self :					Dict						):


							"""simple docstring"""




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


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






import os
from string import ascii_letters

lowerCamelCase__           =				ascii_letters + ' \t\n'



def 							_lowerCamelCase(				)  ->   dict[str, None]:
		__snake_case		       =     os.path.split(os.path.realpath(__snake_case	)	)
		__snake_case		       =     {}
		with open(path[0] + "/dictionary.txt"	) as dictionary_file:
				for word in dictionary_file.read().split("\n"	):
						__snake_case		       =     None
		return english_words


lowerCamelCase__           =				load_dictionary()



def 							_lowerCamelCase(				__snake_case	)  ->   float:
		__snake_case		       =     message.upper()
		__snake_case		       =     remove_non_letters(__snake_case	)
		__snake_case		       =     message.split()
		__snake_case		       =     len([word for word in possible_words if word in ENGLISH_WORDS]	)
		return float(__snake_case	) / len(__snake_case	)



def 							_lowerCamelCase(				__snake_case	)  ->   str:
		return "".join(symbol for symbol in message if symbol in LETTERS_AND_SPACE	)



def 							_lowerCamelCase(				__snake_case						,						__snake_case = 20						,						__snake_case = 85	)  ->   bool:
		__snake_case		       =     get_english_count(__snake_case	) * 100 >= word_percentage
		__snake_case		       =     len(remove_non_letters(__snake_case	)	)
		__snake_case		       =     (float(__snake_case	) / len(__snake_case	)) * 100
		__snake_case		       =     message_letters_percentage >= letter_percentage
		return words_match and letters_match


if __name__ == "__main__":
		import doctest

		doctest.testmod()





