






'''simple docstring'''



from __future__ import annotations

import math
class UpperCAmelCase_					:




      """simple docstring"""




      def __init__( self			:		List[str]     ,      UpperCAmelCase			:		int		)  ->  None:


       '''simple docstring'''

       lowercase					:   int				  =size
       # approximate the overall size of segment tree with given value
       lowercase					:   int				  =[0 for i in range(0     ,      4 * size		)]
       # create array to store lazy update
       lowercase					:   Dict				  =[0 for i in range(0     ,      4 * size		)]
       lowercase					:   Optional[Any]				  =[0 for i in range(0     ,      4 * size		)]  # flag for lazy update






      def 				A__      ( self			:		Any     ,      UpperCAmelCase			:		int		)  ->  int:


       '''simple docstring'''

       return idx * 2






      def 				A__      ( self			:		int     ,      UpperCAmelCase			:		int		)  ->  int:


       '''simple docstring'''

       return idx * 2 + 1






      def 				A__      ( self			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		list[int]		)  ->  None:


       '''simple docstring'''

       if left_element == right_element:
        lowercase					:   int				  =a[left_element - 1]
       else:
        lowercase					:   Union[str, Any]				  =(left_element + right_element) // 2
        self.build(self.left(UpperCAmelCase		)     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase		)
        self.build(self.right(UpperCAmelCase		)     ,      mid + 1     ,      UpperCAmelCase     ,      UpperCAmelCase		)
        lowercase					:   Any				  =max(
            self.segment_tree[self.left(UpperCAmelCase		)]     ,      self.segment_tree[self.right(UpperCAmelCase		)]		)






      def 				A__      ( self			:		Dict     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int		)  ->  bool:


       '''simple docstring'''

       if self.flag[idx] is True:
        lowercase					:   Any				  =self.lazy[idx]
        lowercase					:   Any				  =False
        if left_element != right_element:
         lowercase					:   Tuple				  =self.lazy[idx]
         lowercase					:   Dict				  =self.lazy[idx]
         lowercase					:   Tuple				  =True
         lowercase					:   int				  =True

       if right_element < a or left_element > b:
        return True
       if left_element >= a and right_element <= b:
        lowercase					:   str				  =val
        if left_element != right_element:
         lowercase					:   Optional[int]				  =val
         lowercase					:   Any				  =val
         lowercase					:   int				  =True
         lowercase					:   int				  =True
        return True
       lowercase					:   Optional[int]				  =(left_element + right_element) // 2
       self.update(self.left(UpperCAmelCase		)     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase		)
       self.update(self.right(UpperCAmelCase		)     ,      mid + 1     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase		)
       lowercase					:   List[Any]				  =max(
           self.segment_tree[self.left(UpperCAmelCase		)]     ,      self.segment_tree[self.right(UpperCAmelCase		)]		)
       return True






      def 				A__      ( self			:		Optional[int]     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int     ,      UpperCAmelCase			:		int		)  ->  int | float:


       '''simple docstring'''

       if self.flag[idx] is True:
        lowercase					:   Union[str, Any]				  =self.lazy[idx]
        lowercase					:   int				  =False
        if left_element != right_element:
         lowercase					:   List[str]				  =self.lazy[idx]
         lowercase					:   Tuple				  =self.lazy[idx]
         lowercase					:   Dict				  =True
         lowercase					:   Tuple				  =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]
       lowercase					:   Any				  =(left_element + right_element) // 2
       lowercase					:   int				  =self.query(self.left(UpperCAmelCase		)     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase		)
       lowercase					:   str				  =self.query(self.right(UpperCAmelCase		)     ,      mid + 1     ,      UpperCAmelCase     ,      UpperCAmelCase     ,      UpperCAmelCase		)
       return max(UpperCAmelCase     ,      UpperCAmelCase		)






      def __str__( self			:		Tuple		)  ->  str:


       '''simple docstring'''

       return str([self.query(1     ,      1     ,      self.size     ,      UpperCAmelCase     ,      UpperCAmelCase		) for i in range(1     ,      self.size + 1		)]		)


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











'''simple docstring'''



import mpmath  # for roots of unity
import numpy as np
class UpperCAmelCase_					:




      """simple docstring"""




      def __init__( self			:		List[Any]     ,      UpperCAmelCase			:		Dict=None     ,      UpperCAmelCase			:		Optional[int]=None		)  ->  Optional[Any]:


       '''simple docstring'''

       lowercase					:   Any				  =list(poly_a or [0]		)[:]
       lowercase					:   Dict				  =list(poly_b or [0]		)[:]

       # Remove leading zero coefficients
       while self.polyA[-1] == 0:
        self.polyA.pop()
       lowercase					:   int				  =len(self.polyA		)

       while self.polyB[-1] == 0:
        self.polyB.pop()
       lowercase					:   List[str]				  =len(self.polyB		)

       # Add 0 to make lengths equal a power of 2
       lowercase					:   Tuple				  =int(
           2 ** np.ceil(np.loga(len(self.polyA		) + len(self.polyB		) - 1		)		)		)

       while len(self.polyA		) < self.c_max_length:
        self.polyA.append(0		)
       while len(self.polyB		) < self.c_max_length:
        self.polyB.append(0		)
       # A complex root used for the fourier transform
       lowercase					:   Optional[int]				  =complex(mpmath.root(x=1     ,      n=self.c_max_length     ,      k=1		)		)

       # The product
       lowercase					:   str				  =self.__multiply()






      def 				A__      ( self			:		Optional[Any]     ,      UpperCAmelCase			:		Union[str, Any]		)  ->  Tuple:


       '''simple docstring'''

       lowercase					:   Tuple				  =[[x] for x in self.polyA] if which == '''A''' else [[x] for x in self.polyB]
       # Corner case
       if len(UpperCAmelCase		) <= 1:
        return dft[0]
       #
       lowercase					:   List[Any]				  =self.c_max_length // 2
       while next_ncol > 0:
        lowercase					:   str				  =[[] for i in range(UpperCAmelCase		)]
        lowercase					:   List[str]				  =self.root**next_ncol

        # First half of next step
        lowercase					:   Union[str, Any]				  =1
        for j in range(self.c_max_length // (next_ncol * 2)		):
         for i in range(UpperCAmelCase		):
          new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]		)
         current_root *= root
        # Second half of next step
        lowercase					:   Any				  =1
        for j in range(self.c_max_length // (next_ncol * 2)		):
         for i in range(UpperCAmelCase		):
          new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]		)
         current_root *= root
        # Update
        lowercase					:   Tuple				  =new_dft
        lowercase					:   List[Any]				  =next_ncol // 2
       return dft[0]






      def 				A__      ( self			:		int		)  ->  str:


       '''simple docstring'''

       lowercase					:   List[Any]				  =self.__dft('''A'''		)
       lowercase					:   Union[str, Any]				  =self.__dft('''B'''		)
       lowercase					:   Any				  =[[dft_a[i] * dft_b[i] for i in range(self.c_max_length		)]]
       del dft_a
       del dft_b

       # Corner Case
       if len(inverce_c[0]		) <= 1:
        return inverce_c[0]
       # Inverse DFT
       lowercase					:   Tuple				  =2
       while next_ncol <= self.c_max_length:
        lowercase					:   Tuple				  =[[] for i in range(UpperCAmelCase		)]
        lowercase					:   Tuple				  =self.root ** (next_ncol // 2)
        lowercase					:   Optional[int]				  =1
        # First half of next step
        for j in range(self.c_max_length // next_ncol		):
         for i in range(next_ncol // 2		):
          # Even positions
          new_inverse_c[i].append(
              (
                  inverce_c[i][j]
                  + inverce_c[i][j + self.c_max_length // next_ncol]
              )
              / 2		)
          # Odd positions
          new_inverse_c[i + next_ncol // 2].append(
              (
                  inverce_c[i][j]
                  - inverce_c[i][j + self.c_max_length // next_ncol]
              )
              / (2 * current_root)		)
         current_root *= root
        # Update
        lowercase					:   List[Any]				  =new_inverse_c
        next_ncol *= 2
       # Unpack
       lowercase					:   List[str]				  =[round(x[0].real     ,      8		) + round(x[0].imag     ,      8		) * 1J for x in inverce_c]

       # Remove leading 0's
       while inverce_c[-1] == 0:
        inverce_c.pop()
       return inverce_c






      def __str__( self			:		Dict		)  ->  Optional[Any]:


       '''simple docstring'''

       lowercase					:   Optional[Any]				  ='''A = ''' + ''' + '''.join(
           f'{coef}*x^{i}' for coef, i in enumerate(self.polyA[: self.len_A]		)		)
       lowercase					:   List[str]				  ='''B = ''' + ''' + '''.join(
           f'{coef}*x^{i}' for coef, i in enumerate(self.polyB[: self.len_B]		)		)
       lowercase					:   Optional[Any]				  ='''A*B = ''' + ''' + '''.join(
           f'{coef}*x^{i}' for coef, i in enumerate(self.product		)		)

       return f'{a}\n{b}\n{c}'


# Unit tests
if __name__ == "__main__":
      import doctest

      doctest.testmod()



