



"""simple docstring"""


import math







class  A_     :



						"""simple docstring"""






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






						def       UpperCAmelCase__	(   self					:List[Any]  ,    lowercase_					:Optional[Any]   )							->     Union[str, Any]:
												return idx * 2






						def       UpperCAmelCase__	(   self					:Dict  ,    lowercase_					:Optional[Any]   )							->     int:
												return idx * 2 + 1






						def       UpperCAmelCase__	(   self					:str  ,    lowercase_					:Union[str, Any]  ,    lowercase_					:Tuple  ,    lowercase_					:Tuple   )							->     Dict:  # noqa: E741
												if l == r:
																		UpperCAmelCase			 =					A[l]
												else:
																		UpperCAmelCase			 =					(l + r) // 2
																		self.build(self.left(lowercase_   )  ,    lowercase_  ,    lowercase_   )
																		self.build(self.right(lowercase_   )  ,    mid + 1  ,    lowercase_   )
																		UpperCAmelCase			 =					max(self.st[self.left(lowercase_   )]  ,    self.st[self.right(lowercase_   )]   )






						def       UpperCAmelCase__	(   self					:Union[str, Any]  ,    lowercase_					:Union[str, Any]  ,    lowercase_					:Optional[Any]  ,    lowercase_					:Optional[Any]   )							->     Any:
												return self.update_recursive(1  ,    0  ,    self.N - 1  ,    a - 1  ,    b - 1  ,    lowercase_   )






						def       UpperCAmelCase__	(   self					:Any  ,    lowercase_					:Optional[Any]  ,    lowercase_					:int  ,    lowercase_					:List[Any]  ,    lowercase_					:List[Any]  ,    lowercase_					:List[str]  ,    lowercase_					:int   )							->     Dict:  # noqa: E741
												if r < a or l > b:
																		return True
												if l == r:
																		UpperCAmelCase			 =					val
																		return True
												UpperCAmelCase			 =					(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_   )
												UpperCAmelCase			 =					max(self.st[self.left(lowercase_   )]  ,    self.st[self.right(lowercase_   )]   )
												return True






						def       UpperCAmelCase__	(   self					:List[str]  ,    lowercase_					:Tuple  ,    lowercase_					:List[str]   )							->     Dict:
												return self.query_recursive(1  ,    0  ,    self.N - 1  ,    a - 1  ,    b - 1   )






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






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


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

import timeit





class 				lowercase    :


   def __init__( self					:						Dict ,		__lowerCAmelCase					:						Any)   ->       Optional[int]:
         if isinstance(__lowerCAmelCase ,		__lowerCAmelCase):  # Initializes a matrix identical to the one provided.
               lowercase_     			=   arg
               lowercase_     			=   len(__lowerCAmelCase)
         else:  # Initializes a square matrix of the given size and set values to zero.
               lowercase_     			=   arg
               lowercase_     			=   [[0 for _ in range(self.n)] for _ in range(self.n)]


   def __mul__( self					:						int ,		__lowerCAmelCase					:						List[str])   ->       Union[str, Any]:
         lowercase_     			=   Matrix(self.n)
         for i in range(self.n):
               for j in range(self.n):
                     for k in range(self.n):
                           matrix.t[i][j] += self.t[i][k] * b.t[k][j]
         return matrix




def __a			(						__lowerCamelCase      :    List[str]			,		__lowerCamelCase      :    Dict					)						->				Optional[Any]:
      '''simple docstring'''


      lowercase_     			=   Matrix([[1, 0], [0, 1]]					)
      while b > 0:
            if b & 1:
                  matrix *= a
            a *= a
            b >>= 1
      return matrix


def __a			(						__lowerCamelCase      :    Tuple			,		__lowerCamelCase      :    Tuple			,		__lowerCamelCase      :    List[Any]					)						->				Dict:
      '''simple docstring'''


      if n == 1:
            return fa
      elif n == 2:
            return fa
      lowercase_     			=   Matrix([[1, 1], [1, 0]]					)
      lowercase_     			=   modular_exponentiation(__lowerCamelCase			,		n - 2					)
      return fa * matrix.t[0][0] + fa * matrix.t[0][1]


def __a			(						__lowerCamelCase      :    List[Any]			,		__lowerCamelCase      :    Union[str, Any]			,		__lowerCamelCase      :    List[str]					)						->				Optional[Any]:
      '''simple docstring'''


      if n == 1:
            return fa
      elif n == 2:
            return fa

      lowercase_     			=   fa
      lowercase_     			=   fa
      n -= 2

      while n > 0:
            lowercase_			,				lowercase_     			=   fn_a + fn_a, fn_a
            n -= 1

      return fn_a


def __a			(						)						->				str:
      '''simple docstring'''


      lowercase_     			=   "\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
      lowercase_     			=   "fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
      lowercase_     			=   timeit.timeit(setup=__lowerCamelCase			,		stmt=__lowerCamelCase			,		number=100					)
      print("With matrix exponentiation the average execution time is "			,		exec_time / 100					)
      return exec_time


def __a			(						)						->				Optional[Any]:
      '''simple docstring'''


      lowercase_     			=   "\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
      lowercase_     			=   "simple_fibonacci(randint(1,70000), 1, 1)"
      lowercase_     			=   timeit.timeit(setup=__lowerCamelCase			,		stmt=__lowerCamelCase			,		number=100					)
      print(
          "Without matrix exponentiation the average execution time is "			,		exec_time / 100					)
      return exec_time


def __a			(						)						->				Tuple:
      '''simple docstring'''


      matrix_exponentiation_time()
      simple_fibonacci_time()


if __name__ == "__main__":
       main()






