




'''simple docstring'''






from __future__ import annotations

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

A_			      =		TypeVar("T")






class        lowercase_      (						Generic[T]							):





     def __init__(     self     :					str     ,							__lowerCamelCase     :					list[T]     ,							__lowerCamelCase     :					Callable[[T, T], T]			):
           snake_case__       :   Any | T	      =    None

           snake_case__       :   int	      =    len(__lowerCamelCase			)
           snake_case__       :   list[T]	      =    [any_type for _ in range(self.N			)] + arr
           snake_case__       :   Optional[int]	      =    fnc
           self.build()





     def 			_lowerCAmelCase      (     self     :					Optional[int]			):
           for p in range(self.N - 1     ,							0     ,							-1			):
                 snake_case__       :   int	      =    self.fn(self.st[p * 2]     ,							self.st[p * 2 + 1]			)





     def 			_lowerCAmelCase      (     self     :					List[Any]     ,							__lowerCamelCase     :					int     ,							__lowerCamelCase     :					T			):
           p += self.N
           snake_case__       :   Tuple	      =    v
           while p > 1:
                 snake_case__       :   Union[str, Any]	      =    p // 2
                 snake_case__       :   str	      =    self.fn(self.st[p * 2]     ,							self.st[p * 2 + 1]			)





     def 			_lowerCAmelCase      (     self     :					Dict     ,							__lowerCamelCase     :					int     ,							__lowerCamelCase     :					int			):  # noqa: E741
           snake_case__      ,							snake_case__       :   Any	      =    l + self.N, r + self.N

           snake_case__       :   T | None	      =    None
           while l <= r:
                 if l % 2 == 1:
                       snake_case__       :   Tuple	      =    self.st[l] if res is None else self.fn(__lowerCamelCase     ,							self.st[l]			)
                 if r % 2 == 0:
                       snake_case__       :   Dict	      =    self.st[r] if res is None else self.fn(__lowerCamelCase     ,							self.st[r]			)
                 snake_case__      ,							snake_case__       :   Dict	      =    (l + 1) // 2, (r - 1) // 2
           return res


if __name__ == "__main__":
      from functools import reduce

      A_			      =		[1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]

      A_			      =		{
          0: 7,
          1: 2,
          2: 6,
          3: -14,
          4: 5,
          5: 4,
          6: 7,
          7: -10,
          8: 9,
          9: 10,
          10: 12,
          11: 1,
      }

      A_			      =		SegmentTree(test_array, min)
      A_			      =		SegmentTree(test_array, max)
      A_			      =		SegmentTree(test_array, lambda a, b: a + b)






      def 		UpperCamelCase__      (		)    ->   None:
            for i in range(len(__SCREAMING_SNAKE_CASE		)		):
                  for j in range(__SCREAMING_SNAKE_CASE				,      len(__SCREAMING_SNAKE_CASE		)		):
                        snake_case__       :   Dict	      =    reduce(__SCREAMING_SNAKE_CASE				,      test_array[i : j + 1]		)
                        snake_case__       :   Tuple	      =    reduce(__SCREAMING_SNAKE_CASE				,      test_array[i : j + 1]		)
                        snake_case__       :   Tuple	      =    reduce(lambda __SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		: a + b				,      test_array[i : j + 1]		)
                        assert min_range == min_segment_tree.query(__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		)
                        assert max_range == max_segment_tree.query(__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		)
                        assert sum_range == sum_segment_tree.query(__SCREAMING_SNAKE_CASE				,      __SCREAMING_SNAKE_CASE		)

      test_all_segments()

      for index, value in test_updates.items():
            A_			      =		value
            min_segment_tree.update(index, value)
            max_segment_tree.update(index, value)
            sum_segment_tree.update(index, value)
            test_all_segments()






'''simple docstring'''






from typing import Any






class        lowercase_      :





     def __init__(     self     :					Dict     ,							__lowerCamelCase     :					Any			):
           snake_case__       :   str	      =    data
           snake_case__       :   Dict	      =    None






class        lowercase_      :





     def __init__(     self     :					int			):
           snake_case__       :   List[Any]	      =    None





     def 			_lowerCAmelCase      (     self     :					str			):
           snake_case__       :   Any	      =    self.head
           while temp is not None:
                 print(temp.data     ,							end=' '			)
                 snake_case__       :   int	      =    temp.next
           print()





     def 			_lowerCAmelCase      (     self     :					Optional[Any]     ,							__lowerCamelCase     :					Any			):
           snake_case__       :   Union[str, Any]	      =    Node(__lowerCamelCase			)
           snake_case__       :   List[str]	      =    self.head
           snake_case__       :   Any	      =    new_node





     def 			_lowerCAmelCase      (     self     :					Dict     ,							__lowerCamelCase     :					int     ,							__lowerCamelCase     :					Tuple			):
           if node_data_a == node_data_a:
                 return
           else:
                 snake_case__       :   List[Any]	      =    self.head
                 while node_a is not None and node_a.data != node_data_a:
                       snake_case__       :   List[str]	      =    node_a.next

                 snake_case__       :   Union[str, Any]	      =    self.head
                 while node_a is not None and node_a.data != node_data_a:
                       snake_case__       :   str	      =    node_a.next

                 if node_a is None or node_a is None:
                       return

                 snake_case__      ,							snake_case__       :   Dict	      =    node_a.data, node_a.data


if __name__ == "__main__":
      A_			      =		LinkedList()
      for i in range(5, 0, -1):
            ll.push(i)

      ll.print_list()

      ll.swap_nodes(1, 4)
      print("After swapping")
      ll.print_list()
