




"""simple docstring"""







from collections.abc import Sequence
from queue import Queue






class       SCREAMING_SNAKE_CASE__					:


      def __init__(							self				:			List[Any]						,						lowerCAmelCase				:			Optional[Any]						,						lowerCAmelCase				:			Union[str, Any]						,						lowerCAmelCase				:			Dict						,						lowerCAmelCase				:			Union[str, Any]=None						,						lowerCAmelCase				:			int=None					):
          lowerCAmelCase  =				start
          lowerCAmelCase  =				end
          lowerCAmelCase  =				val
          lowerCAmelCase  =				(start + end) // 2
          lowerCAmelCase  =				left
          lowerCAmelCase  =				right




      def __repr__(							self				:			List[Any]					):
          return f'''SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'''






class       SCREAMING_SNAKE_CASE__					:


      def __init__(							self				:			List[str]						,						lowerCAmelCase				:			Sequence						,						lowerCAmelCase				:			Optional[int]					):
          lowerCAmelCase  =				collection
          lowerCAmelCase  =				function
          if self.collection:
              lowerCAmelCase  =				self._build_tree(0						,						len(lowerCAmelCase					) - 1					)


      def   __lowercase (							self				:			Tuple						,						lowerCAmelCase				:			Union[str, Any]						,						lowerCAmelCase				:			Tuple					):
          self._update_tree(self.root						,						lowerCAmelCase						,						lowerCAmelCase					)


      def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			List[str]						,						lowerCAmelCase				:			str					):
          return self._query_range(self.root						,						lowerCAmelCase						,						lowerCAmelCase					)


      def   __lowercase (							self				:			Tuple						,						lowerCAmelCase				:			Union[str, Any]						,						lowerCAmelCase				:			Any					):
          if start == end:
              return SegmentTreeNode(lowerCAmelCase						,						lowerCAmelCase						,						self.collection[start]					)
          lowerCAmelCase  =				(start + end) // 2
          lowerCAmelCase  =				self._build_tree(lowerCAmelCase						,						lowerCAmelCase					)
          lowerCAmelCase  =				self._build_tree(mid + 1						,						lowerCAmelCase					)
          return SegmentTreeNode(lowerCAmelCase						,						lowerCAmelCase						,						self.fn(left.val						,						right.val					)						,						lowerCAmelCase						,						lowerCAmelCase					)


      def   __lowercase (							self				:			List[Any]						,						lowerCAmelCase				:			Tuple						,						lowerCAmelCase				:			List[Any]						,						lowerCAmelCase				:			int					):
          if node.start == i and node.end == i:
              lowerCAmelCase  =				val
              return
          if i <= node.mid:
              self._update_tree(node.left						,						lowerCAmelCase						,						lowerCAmelCase					)
          else:
              self._update_tree(node.right						,						lowerCAmelCase						,						lowerCAmelCase					)
          lowerCAmelCase  =				self.fn(node.left.val						,						node.right.val					)


      def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			Tuple						,						lowerCAmelCase				:			Dict						,						lowerCAmelCase				:			Union[str, Any]					):
          if node.start == i and node.end == j:
              return node.val

          if i <= node.mid:
              if j <= node.mid:
                  # range in left child tree
                  return self._query_range(node.left						,						lowerCAmelCase						,						lowerCAmelCase					)
              else:
                  # range in left child tree and right child tree
                  return self.fn(
                      self._query_range(node.left						,						lowerCAmelCase						,						node.mid					)						,						self._query_range(node.right						,						node.mid + 1						,						lowerCAmelCase					)						,						)
          else:
              # range in right child tree
              return self._query_range(node.right						,						lowerCAmelCase						,						lowerCAmelCase					)




      def   __lowercase (							self				:			Tuple					):
          if self.root is not None:
              lowerCAmelCase  =				Queue()
              queue.put(self.root					)
              while not queue.empty():
                  lowerCAmelCase  =				queue.get()
                  yield node

                  if node.left is not None:
                      queue.put(node.left					)

                  if node.right is not None:
                      queue.put(node.right					)


if __name__ == "__main__":
  import operator

  for fn in [operator.add, max, min]:
    print('*' * 5_0)
    a      =							SegmentTree([2, 1, 5, 3, 4], fn)
    for node in arr.traverse():
      print(node)
    print()

    arr.update(1, 5)
    for node in arr.traverse():
      print(node)
    print()

    print(arr.query_range(3, 4))  # 7
    print(arr.query_range(2, 2))  # 5
    print(arr.query_range(1, 3))  # 13
    print()











"""simple docstring"""







from queue import PriorityQueue
from typing import Any

import numpy as np





def 							lowercase					(snake_case__   : dict      ,       snake_case__   : str      ,       snake_case__   : set      ,       snake_case__   : set      ,       snake_case__   : dict      ,       snake_case__   : dict      ,       snake_case__   : PriorityQueue      ,       snake_case__   : dict      ,       snake_case__   : float | int      ,       )     ->  float | int:


				'''simple docstring'''






				for nxt, d in graph[v]:
								if nxt in visited_forward:
												continue
								lowerCAmelCase  =				cst_fwd.get(snake_case__      ,       np.inf )
								lowerCAmelCase  =				cst_fwd[v] + d
								if new_cost_f < old_cost_f:
												queue.put((new_cost_f, nxt) )
												lowerCAmelCase  =				new_cost_f
												lowerCAmelCase  =				v
								if nxt in visited_backward:
												if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
																lowerCAmelCase  =				cst_fwd[v] + d + cst_bwd[nxt]
				return shortest_distance





def 							lowercase					(snake_case__   : str      ,       snake_case__   : str      ,       snake_case__   : dict      ,       snake_case__   : dict )     ->  int:


				'''simple docstring'''






				lowerCAmelCase  =				-1

				lowerCAmelCase  =				set()
				lowerCAmelCase  =				set()
				lowerCAmelCase  =				{source: 0}
				lowerCAmelCase  =				{destination: 0}
				lowerCAmelCase  =				{source: None}
				lowerCAmelCase  =				{destination: None}
				lowerCAmelCase  =				PriorityQueue()
				lowerCAmelCase  =				PriorityQueue()

				lowerCAmelCase  =				np.inf

				queue_forward.put((0, source) )
				queue_backward.put((0, destination) )

				if source == destination:
								return 0

				while not queue_forward.empty() and not queue_backward.empty():
								lowerCAmelCase ,						lowerCAmelCase  =				queue_forward.get()
								visited_forward.add(snake_case__ )

								lowerCAmelCase ,						lowerCAmelCase  =				queue_backward.get()
								visited_backward.add(snake_case__ )

								lowerCAmelCase  =				pass_and_relaxation(
								    snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       )

								lowerCAmelCase  =				pass_and_relaxation(
								    snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       )

								if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
												break

				if shortest_distance != np.inf:
								lowerCAmelCase  =				shortest_distance
				return shortest_path_distance


a      =							{
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}
a      =							{
    'B': [['E', 1]],
    'C': [['B', 1]],
    'D': [['C', 1]],
    'F': [['D', 1], ['G', 1]],
    'E': [[None, np.inf]],
    'G': [['E', 2]],
}

if __name__ == "__main__":
		import doctest

		doctest.testmod()





