
import math






class     a_       :



       """simple docstring"""






       def __init__(		self				,       _lowerCamelCase   )					->List[Any]:
           SCREAMING_SNAKE_CASE				:				List[Any]				      = len(lowercase_   )
           SCREAMING_SNAKE_CASE				:				Optional[Any]				      = [0] * (
               4 * self.N
           )  # approximate the overall size of segment tree with array N
           self.build(1				,       0				,       self.N - 1   )






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase   )					->Dict:
           return idx * 2






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase   )					->str:
           return idx * 2 + 1






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase   )					->Any:  # noqa: E741
           if l == r:
               SCREAMING_SNAKE_CASE				:				str				      = A[l]
           else:
               SCREAMING_SNAKE_CASE				:				int				      = (l + r) // 2
               self.build(self.left(lowercase_   )				,       lowercase_				,       lowercase_   )
               self.build(self.right(lowercase_   )				,       mid + 1				,       lowercase_   )
               SCREAMING_SNAKE_CASE				:				int				      = max(self.st[self.left(lowercase_   )]				,       self.st[self.right(lowercase_   )]   )






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase   )					->Optional[int]:
           return self.update_recursive(1				,       0				,       self.N - 1				,       a - 1				,       b - 1				,       lowercase_   )






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase   )					->str:  # noqa: E741
           if r < a or l > b:
               return True
           if l == r:
               SCREAMING_SNAKE_CASE				:				Dict				      = val
               return True
           SCREAMING_SNAKE_CASE				:				Any				      = (l + r) // 2
           self.update_recursive(self.left(lowercase_   )				,       lowercase_				,       lowercase_				,       lowercase_				,       lowercase_				,       lowercase_   )
           self.update_recursive(self.right(lowercase_   )				,       mid + 1				,       lowercase_				,       lowercase_				,       lowercase_				,       lowercase_   )
           SCREAMING_SNAKE_CASE				:				Dict				      = max(self.st[self.left(lowercase_   )]				,       self.st[self.right(lowercase_   )]   )
           return True






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase				,       _lowerCamelCase   )					->int:
           return self.query_recursive(1				,       0				,       self.N - 1				,       a - 1				,       b - 1   )






       def 	__lowerCAmelCase     (		self				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase				,       _lowerCamelCase   )					->Any:  # noqa: E741
           if r < a or l > b:
               return -math.inf
           if l >= a and r <= b:
               return self.st[idx]
           SCREAMING_SNAKE_CASE				:				Union[str, Any]				      = (l + r) // 2
           SCREAMING_SNAKE_CASE				:				List[str]				      = self.query_recursive(self.left(lowercase_   )				,       lowercase_				,       lowercase_				,       lowercase_				,       lowercase_   )
           SCREAMING_SNAKE_CASE				:				List[Any]				      = self.query_recursive(self.right(lowercase_   )				,       mid + 1				,       lowercase_				,       lowercase_				,       lowercase_   )
           return max(lowercase_				,       lowercase_   )






       def 	__lowerCAmelCase     (		self   )					->str:
           SCREAMING_SNAKE_CASE				:				Optional[Any]				      = []
           for i in range(1				,       N + 1   ):
               show_list += [self.query(lowercase_				,       lowercase_   )]
           print(lowercase_   )


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



"""simple docstring"""





def 							_lowerCAmelCase   (    UpperCAmelCase  :				int   ,				UpperCAmelCase  :				int   ,				UpperCAmelCase  :				int					):


					'''simple docstring'''






					if power < 0:
										return -1
					base %= mod
					UpperCamelCase__		:     Any								=1

					while power > 0:
										if power & 1:
															UpperCamelCase__		:     Optional[Any]								=(result * base) % mod
										UpperCamelCase__		:     Union[str, Any]								=power >> 1
										UpperCamelCase__		:     Union[str, Any]								=(base * base) % mod

					return result



def 							_lowerCAmelCase   (    ):


					'''simple docstring'''






					print(modular_exponential(3   ,				200   ,				13					)					)


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				main()


