




from dataclasses import dataclass

UpperCamelCase__            =     """0.1"""
UpperCamelCase__            =     """Lucia Harcekova"""
@dataclass
class      a__       :
						_a				:       int
						_a				:       int
						_a				:       str






						def __repr__(  self     ):




											"""simple docstring"""



											return f"""({self.offset}, {self.length}, {self.indicator})"""






class      a__       :






						def __init__(  self						,     _A = 1_3						,     _A = 6     ):




											"""simple docstring"""



											__lowerCAmelCase							  =			window_size
											__lowerCAmelCase							  =			lookahead_buffer_size
											__lowerCAmelCase							  =			self.window_size - self.lookahead_buffer_size






						def 							__SCREAMING_SNAKE_CASE(  self						,     _A     ):




											"""simple docstring"""



											__lowerCAmelCase							  =			[]
											__lowerCAmelCase							  =			''

											# while there are still characters in text to compress
											while text:
																# find the next encoding phrase
																# - triplet with offset, length, indicator (the next encoding character)
																__lowerCAmelCase							  =			self._find_encoding_token(_snake_case						,     _snake_case     )

																# update the search buffer:
																# - add new characters from text into it
																# - check if size exceed the max search buffer size, if so, drop the
																#   oldest elements
																search_buffer += text[: token.length + 1]
																if len(_snake_case     ) > self.search_buffer_size:
																					__lowerCAmelCase							  =			search_buffer[-self.search_buffer_size :]

																# update the text
																__lowerCAmelCase							  =			text[token.length + 1 :]

																# append the token to output
																output.append(_snake_case     )

											return output






						def 							__SCREAMING_SNAKE_CASE(  self						,     _A     ):




											"""simple docstring"""



											__lowerCAmelCase							  =			''

											for token in tokens:
																for _ in range(token.length     ):
																					output += output[-token.offset]
																output += token.indicator

											return output






						def 							__SCREAMING_SNAKE_CASE(  self						,     _A						,     _A     ):




											"""simple docstring"""



											if not text:
																raise ValueError("We need some text to work with."     )

											# Initialise result parameters to default values
											__lowerCAmelCase							  =			0, 0

											if not search_buffer:
																return Token(_snake_case						,     _snake_case						,     text[length]     )

											for i, character in enumerate(_snake_case     ):
																__lowerCAmelCase							  =			len(_snake_case     ) - i
																if character == text[0]:
																					__lowerCAmelCase							  =			self._match_length_from_index(_snake_case						,     _snake_case						,     0						,     _snake_case     )
																					# if the found length is bigger than the current or if it's equal,
																					# which means it's offset is smaller: update offset and length
																					if found_length >= length:
																										__lowerCAmelCase							  =			found_offset, found_length

											return Token(_snake_case						,     _snake_case						,     text[length]     )






						def 							__SCREAMING_SNAKE_CASE(  self						,     _A						,     _A						,     _A						,     _A     ):




											"""simple docstring"""



											if not text or text[text_index] != window[window_index]:
																return 0
											return 1 + self._match_length_from_index(
											    _snake_case						,     window + text[text_index]						,     text_index + 1						,     window_index + 1     )


if __name__ == "__main__":
					from doctest import testmod

					testmod()
					# Initialize compressor class
					UpperCamelCase__            =     LZaaCompressor(window_size=13, lookahead_buffer_size=6)

					# Example
					UpperCamelCase__            =     """cabracadabrarrarrad"""
					UpperCamelCase__            =     lzaa_compressor.compress(TEXT)
					print(lzaa_compressor.compress("""ababcbababaa"""))
					UpperCamelCase__            =     lzaa_compressor.decompress(compressed_text)
					assert decompressed_text == TEXT, "The LZ77 algorithm returned the invalid result."












import math




class 	lowerCamelCase__				:






      def __init__(self					:    int		,		_snake_case					:    Dict		)       ->   Union[str, Any]:


       """simple docstring"""






       lowerCamelCase_							:    Optional[Any]							=     len(_snake_case		)
       lowerCamelCase_							:    Optional[Any]							=     [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[str]		,		_snake_case					:    List[str]		)       ->   int:


       """simple docstring"""






       return idx * 2






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    Dict		)       ->   Optional[Any]:


       """simple docstring"""






       return idx * 2 + 1






      def      UpperCAmelCase_     (self					:    List[Any]		,		_snake_case					:    List[Any]		,		_snake_case					:    str		,		_snake_case					:    List[Any]		)       ->   Optional[Any]:  # noqa: E741


       """simple docstring"""






       if l == r:
        lowerCamelCase_							:    List[Any]							=     A[l]
       else:
        lowerCamelCase_							:    int							=     (l + r) // 2
        self.build(self.left(_snake_case		)		,		_snake_case		,		_snake_case		)
        self.build(self.right(_snake_case		)		,		mid + 1		,		_snake_case		)
        lowerCamelCase_							:    Tuple							=     max(self.st[self.left(_snake_case		)]		,		self.st[self.right(_snake_case		)]		)






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    Tuple		,		_snake_case					:    Any		,		_snake_case					:    str		)       ->   Tuple:


       """simple docstring"""






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






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    List[str]		,		_snake_case					:    Tuple		,		_snake_case					:    Optional[int]		,		_snake_case					:    int		,		_snake_case					:    Tuple		,		_snake_case					:    List[str]		)       ->   Optional[Any]:  # noqa: E741


       """simple docstring"""






       if r < a or l > b:
        return True
       if l == r:
        lowerCamelCase_							:    Tuple							=     val
        return True
       lowerCamelCase_							:    Optional[int]							=     (l + r) // 2
       self.update_recursive(self.left(_snake_case		)		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		)
       self.update_recursive(self.right(_snake_case		)		,		mid + 1		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		)
       lowerCamelCase_							:    Union[str, Any]							=     max(self.st[self.left(_snake_case		)]		,		self.st[self.right(_snake_case		)]		)
       return True






      def      UpperCAmelCase_     (self					:    List[Any]		,		_snake_case					:    List[Any]		,		_snake_case					:    Optional[int]		)       ->   str:


       """simple docstring"""






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






      def      UpperCAmelCase_     (self					:    Any		,		_snake_case					:    List[Any]		,		_snake_case					:    Optional[Any]		,		_snake_case					:    int		,		_snake_case					:    Optional[int]		,		_snake_case					:    Optional[Any]		)       ->   str:  # noqa: E741


       """simple docstring"""






       if r < a or l > b:
        return -math.inf
       if l >= a and r <= b:
        return self.st[idx]
       lowerCamelCase_							:    int							=     (l + r) // 2
       lowerCamelCase_							:    Optional[Any]							=     self.query_recursive(self.left(_snake_case		)		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		)
       lowerCamelCase_							:    Union[str, Any]							=     self.query_recursive(self.right(_snake_case		)		,		mid + 1		,		_snake_case		,		_snake_case		,		_snake_case		)
       return max(_snake_case		,		_snake_case		)






      def      UpperCAmelCase_     (self					:    str		)       ->   Tuple:


       """simple docstring"""






       lowerCamelCase_							:    Dict							=     []
       for i in range(1		,		N + 1		):
        show_list += [self.query(_snake_case		,		_snake_case		)]
       print(_snake_case		)


if __name__ == "__main__":
       UpperCamelCase											=      [1, 2, -4, 7, 3, -5, 6, 1_1, -2_0, 9, 1_4, 1_5, 5, 2, -8]
       UpperCamelCase											=      1_5
       UpperCamelCase											=      SegmentTree(A)
       print(segt.query(4, 6))
       print(segt.query(7, 1_1))
       print(segt.query(7, 1_2))
       segt.update(1, 3, 1_1_1)
       print(segt.query(1, 1_5))
       segt.update(7, 8, 2_3_5)
       segt.show_data()
