

'''simple docstring'''




from __future__ import annotations

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

_lowerCAmelCase         =						TypeVar("T")






class   _SCREAMING_SNAKE_CASE   (   Generic[T]     ):



 def __init__(   self		:   Any			,				a__		:   list[T]			,				a__		:   Callable[[T, T], T]      ):
      __magic_name__						       =    None

      __magic_name__						       =    len(_UpperCAmelCase      )
      __magic_name__						       =    [any_type for _ in range(self.N      )] + arr
      __magic_name__						       =    fnc
      self.build()



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



 def 			snake_case__  (   self		:   List[str]			,				a__		:   int			,				a__		:   T      ):
      p += self.N
      __magic_name__						       =    v
      while p > 1:
           __magic_name__						       =    p // 2
           __magic_name__						       =    self.fn(self.st[p * 2]			,				self.st[p * 2 + 1]      )



 def 			snake_case__  (   self		:   str			,				a__		:   int			,				a__		:   int      ):  # noqa: E741
      __magic_name__						       =    l + self.N, r + self.N

      __magic_name__						       =    None
      while l <= r:
           if l % 2 == 1:
                __magic_name__						       =    self.st[l] if res is None else self.fn(_UpperCAmelCase			,				self.st[l]      )
           if r % 2 == 0:
                __magic_name__						       =    self.st[r] if res is None else self.fn(_UpperCAmelCase			,				self.st[r]      )
           __magic_name__						       =    (l + 1) // 2, (r - 1) // 2
      return res


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

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

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

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




  def 						UpperCamelCase	(			)				->     None:






       '''simple docstring'''
       for i in range(len(lowerCAmelCase_			)			):
            for j in range(lowerCAmelCase_		,						len(lowerCAmelCase_			)			):
                 __magic_name__						       =    reduce(lowerCAmelCase_		,						test_array[i : j + 1]			)
                 __magic_name__						       =    reduce(lowerCAmelCase_		,						test_array[i : j + 1]			)
                 __magic_name__						       =    reduce(lambda a		,						a			: a + b		,						test_array[i : j + 1]			)
                 assert min_range == min_segment_tree.query(lowerCAmelCase_		,						lowerCAmelCase_			)
                 assert max_range == max_segment_tree.query(lowerCAmelCase_		,						lowerCAmelCase_			)
                 assert sum_range == sum_segment_tree.query(lowerCAmelCase_		,						lowerCAmelCase_			)

  test_all_segments()

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









'''simple docstring'''




import functools




def 						UpperCamelCase	(			a		,						a			)				->     int:






     '''simple docstring'''
     __magic_name__						       =    len(a			)
     __magic_name__						       =    len(a			)

     @functools.cache
     def min_distance(a		,						a			) -> int:
          # if first word index is overflow - delete all from the second word
          if indexa >= len_worda:
               return len_worda - indexa
          # if second word index is overflow - delete all from the first word
          if indexa >= len_worda:
               return len_worda - indexa
          __magic_name__						       =    int(worda[indexa] != worda[indexa]			)  # current letters not identical
          return min(
              1 + min_distance(indexa + 1		,						a			)		,						1 + min_distance(a		,						indexa + 1			)		,						diff + min_distance(indexa + 1		,						indexa + 1			)		,						)

     return min_distance(0		,						0			)


if __name__ == "__main__":
      import doctest

      doctest.testmod()






