





from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

UpperCamelCase__           =			TypeVar("T")
UpperCamelCase__           =			TypeVar("U")

class 							__SCREAMING_SNAKE_CASE       (  Generic[T, U]							):






							def __init__(    self	,			__lowerCAmelCase	,			__lowerCAmelCase	):
														UpperCamelCase__					  =      key
														UpperCamelCase__					  =      val
														UpperCamelCase__					  =      None
														UpperCamelCase__					  =      None







							def __repr__(    self	):
														return (
														    f"""Node: key: {self.key}, val: {self.val}, """
														    f"""has next: {bool(self.next	)}, has prev: {bool(self.prev	)}"""
														)






class 							__SCREAMING_SNAKE_CASE       (  Generic[T, U]							):






							def __init__(    self	):
														UpperCamelCase__					  =      DoubleLinkedListNode(_lowerCamelCase	,			_lowerCamelCase	)
														UpperCamelCase__					  =      DoubleLinkedListNode(_lowerCamelCase	,			_lowerCamelCase	)
														UpperCamelCase__					  =      self.rear, self.head






							def __repr__(    self	):
														UpperCamelCase__					  =      ["""DoubleLinkedList"""]
														UpperCamelCase__					  =      self.head
														while node.next is not None:
																					rep.append(str(_lowerCamelCase	)	)
																					UpperCamelCase__					  =      node.next
														rep.append(str(self.rear	)	)
														return ",\n    ".join(_lowerCamelCase	)






							def 					_lowerCamelCase		(    self	,			__lowerCAmelCase	):
														UpperCamelCase__					  =      self.rear.prev

														# All nodes other than self.head are guaranteed to have non-None previous
														assert previous is not None

														UpperCamelCase__					  =      node
														UpperCamelCase__					  =      previous
														UpperCamelCase__					  =      node
														UpperCamelCase__					  =      self.rear







							def 					_lowerCamelCase		(    self	,			__lowerCAmelCase	):

														if node.prev is None or node.next is None:
																					return None

														UpperCamelCase__					  =      node.next
														UpperCamelCase__					  =      node.prev
														UpperCamelCase__					  =      None
														UpperCamelCase__					  =      None
														return node






class 							__SCREAMING_SNAKE_CASE       (  Generic[T, U]							):
							snake_case  :   Union[str, Any]      =							{}






							def __init__(    self	,			__lowerCAmelCase	):
														UpperCamelCase__					  =      DoubleLinkedList()
														UpperCamelCase__					  =      capacity
														UpperCamelCase__					  =      0
														UpperCamelCase__					  =      0
														UpperCamelCase__					  =      0
														UpperCamelCase__					  =      {}






							def __repr__(    self	):
														return (
														    f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
														    f"""capacity={self.capacity}, current size={self.num_keys})"""
														)






							def __contains__(    self	,			__lowerCAmelCase	):
														return key in self.cache






							def 					_lowerCamelCase		(    self	,			__lowerCAmelCase	):

														if key in self.cache:
																					self.hits += 1
																					UpperCamelCase__					  =      self.cache[key]
																					UpperCamelCase__					  =      self.list.remove(self.cache[key]	)
																					assert node == value_node

																					# node is guaranteed not None because it is in self.cache
																					assert node is not None
																					self.list.add(_lowerCamelCase	)
																					return node.val
														self.miss += 1
														return None






							def 					_lowerCamelCase		(    self	,			__lowerCAmelCase	,			__lowerCAmelCase	):

														if key not in self.cache:
																					if self.num_keys >= self.capacity:
																												# delete first node (oldest) when over capacity
																												UpperCamelCase__					  =      self.list.head.next

																												# guaranteed to have a non-None first node when num_keys > 0
																												# explain to type checker via assertions
																												assert first_node is not None
																												assert first_node.key is not None
																												assert (
																												    self.list.remove(_lowerCamelCase	) is not None
																												)  # node guaranteed to be in list assert node.key is not None

																												del self.cache[first_node.key]
																												self.num_keys -= 1
																					UpperCamelCase__					  =      DoubleLinkedListNode(_lowerCamelCase	,			_lowerCamelCase	)
																					self.list.add(self.cache[key]	)
																					self.num_keys += 1

														else:
																					# bump node to the end of the list, update value
																					UpperCamelCase__					  =      self.list.remove(self.cache[key]	)
																					assert node is not None  # node guaranteed to be in list
																					UpperCamelCase__					  =      value
																					self.list.add(_lowerCamelCase	)







							@classmethod
							def 					_lowerCamelCase		(    cls	,			__lowerCAmelCase = 128	):

														def cache_decorator_inner(__lowerCAmelCase	) -> Callable[..., U]:
																					def cache_decorator_wrapper(*__lowerCAmelCase	) -> U:
																												if func not in cls.decorator_function_to_instance_map:
																																			UpperCamelCase__					  =      LRUCache(_lowerCamelCase	)

																												UpperCamelCase__					  =      cls.decorator_function_to_instance_map[func].get(args[0]	)
																												if result is None:
																																			UpperCamelCase__					  =      func(*_lowerCamelCase	)
																																			cls.decorator_function_to_instance_map[func].put(args[0]	,			_lowerCamelCase	)
																												return result

																					def cache_info() -> LRUCache[T, U]:
																												return cls.decorator_function_to_instance_map[func]

																					setattr(_lowerCamelCase	,			"""cache_info"""	,			_lowerCamelCase	)  # noqa: B010

																					return cache_decorator_wrapper

														return cache_decorator_inner


if __name__ == "__main__":
					import doctest

					doctest.testmod()







"""simple docstring"""
from __future__ import annotations

import math

class       lowerCamelCase	:


  '''simple docstring'''







  def __init__(self							,       _lowerCamelCase	):


        """simple docstring"""

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



  def  _a      (self							,       _lowerCamelCase	):


        """simple docstring"""

        return idx * 2



  def  _a      (self							,       _lowerCamelCase	):


        """simple docstring"""

        return idx * 2 + 1



  def  _a      (self							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

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



  def  _a      (self							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

        if self.flag[idx] is True:
              UpperCAmelCase__			:							Union[str, Any]							=    self.lazy[idx]
              UpperCAmelCase__			:							Dict							=    False
              if left_element != right_element:
                    UpperCAmelCase__			:							Optional[Any]							=    self.lazy[idx]
                    UpperCAmelCase__			:							Optional[int]							=    self.lazy[idx]
                    UpperCAmelCase__			:							Tuple							=    True
                    UpperCAmelCase__			:							str							=    True

        if right_element < a or left_element > b:
              return True
        if left_element >= a and right_element <= b:
              UpperCAmelCase__			:							Union[str, Any]							=    val
              if left_element != right_element:
                    UpperCAmelCase__			:							Union[str, Any]							=    val
                    UpperCAmelCase__			:							List[Any]							=    val
                    UpperCAmelCase__			:							Union[str, Any]							=    True
                    UpperCAmelCase__			:							List[Any]							=    True
              return True
        UpperCAmelCase__			:							Tuple							=    (left_element + right_element) // 2
        self.update(self.left(_lowerCamelCase	)							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase	)
        self.update(self.right(_lowerCamelCase	)							,       mid + 1							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase	)
        UpperCAmelCase__			:							Dict							=    max(
            self.segment_tree[self.left(_lowerCamelCase	)]							,       self.segment_tree[self.right(_lowerCamelCase	)]	)
        return True



  def  _a      (self							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase							,       _lowerCamelCase	):


        """simple docstring"""

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




  def __str__(self	):


        """simple docstring"""

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


if __name__ == "__main__":
    _A							=  [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
    _A							=  15
    _A							=  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, 1_11)
    print(segt.query(1, 1, size, 1, 15))
    segt.update(1, 1, size, 7, 8, 2_35)
    print(segt)

