

from __future__ import annotations

import math







class 				lowercase       :




				def __init__(      self   ,     snake_case ):
											snake_case_           =					size
											# approximate the overall size of segment tree with given value
											snake_case_           =					[0 for i in range(0   ,     4 * size )]
											# create array to store lazy update
											snake_case_           =					[0 for i in range(0   ,     4 * size )]
											snake_case_           =					[0 for i in range(0   ,     4 * size )]  # flag for lazy update




				def 					a							(      self   ,     snake_case ):
											return idx * 2




				def 					a							(      self   ,     snake_case ):
											return idx * 2 + 1




				def 					a							(      self   ,     snake_case   ,     snake_case   ,     snake_case   ,     snake_case ):
											if left_element == right_element:
																		snake_case_           =					a[left_element - 1]
											else:
																		snake_case_           =					(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 )
																		snake_case_           =					max(
																		    self.segment_tree[self.left(snake_case )]   ,     self.segment_tree[self.right(snake_case )] )




				def 					a							(      self   ,     snake_case   ,     snake_case   ,     snake_case   ,     snake_case   ,     snake_case   ,     snake_case ):
											if self.flag[idx] is True:
																		snake_case_           =					self.lazy[idx]
																		snake_case_           =					False
																		if left_element != right_element:
																									snake_case_           =					self.lazy[idx]
																									snake_case_           =					self.lazy[idx]
																									snake_case_           =					True
																									snake_case_           =					True

											if right_element < a or left_element > b:
																		return True
											if left_element >= a and right_element <= b:
																		snake_case_           =					val
																		if left_element != right_element:
																									snake_case_           =					val
																									snake_case_           =					val
																									snake_case_           =					True
																									snake_case_           =					True
																		return True
											snake_case_           =					(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 )
											snake_case_           =					max(
											    self.segment_tree[self.left(snake_case )]   ,     self.segment_tree[self.right(snake_case )] )
											return True




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




				def __str__(      self ):
											return str([self.query(1   ,     1   ,     self.size   ,     snake_case   ,     snake_case ) for i in range(1   ,     self.size + 1 )] )


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







def       __lowerCamelCase			(				UpperCamelCase__ = 50000000   ):







							'''simple docstring'''






							snake_case_           =					set()
							snake_case_           =					int((limit - 24) ** (1 / 2)   )

							snake_case_           =					set(range(3     ,							prime_square_limit + 1     ,							2   )   )
							primes.add(2   )
							for p in range(3     ,							prime_square_limit + 1     ,							2   ):
														if p not in primes:
																					continue
														primes.difference_update(set(range(p * p     ,							prime_square_limit + 1     ,							UpperCamelCase__   )   )   )

							for primea in primes:
														snake_case_           =					primea * primea
														for primea in primes:
																					snake_case_           =					primea * primea * primea
																					if square + cube >= limit - 16:
																												break
																					for primea in primes:
																												snake_case_           =					primea * primea * primea * primea
																												snake_case_           =					square + cube + tetr
																												if total >= limit:
																																			break
																												ret.add(UpperCamelCase__   )

							return len(UpperCamelCase__   )


if __name__ == "__main__":
					print(F'''{solution() = }''')




