
from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

__UpperCAmelCase							=			TypeVar("T")


def       A__      (    __lowerCamelCase		):
   return (position - 1) // 2


def       A__      (    __lowerCamelCase		):
   return (2 * position) + 1


def       A__      (    __lowerCamelCase		):
   return (2 * position) + 2





class 							UpperCamelCase__						(     Generic[T]     ):






       """simple docstring"""


       def __init__(				self     )							->							None:
          SCREAMING_SNAKE_CASE_     =	[]
          SCREAMING_SNAKE_CASE_     =	{}
          SCREAMING_SNAKE_CASE_     =	0



       def __len__(				self     )							->							int:
          return self.elements



       def __repr__(				self     )							->							str:
          return str(self.heap     )



       def   _UpperCamelCase     (				self     )							->							bool:
          # Check if the priority queue is empty
          return self.elements == 0



       def   _UpperCamelCase     (				self      ,			_A      ,			_A     )							->							None:
          # Add an element with given priority to the queue
          self.heap.append((elem, weight)     )
          SCREAMING_SNAKE_CASE_     =	self.elements
          self.elements += 1
          self._bubble_up(__UpperCAmelCase     )



       def   _UpperCamelCase     (				self     )							->							T:
          # Remove and return the element with lowest weight (highest priority)
          if self.elements > 1:
             self._swap_nodes(0      ,			self.elements - 1     )
          SCREAMING_SNAKE_CASE_     =	self.heap.pop()
          del self.position_map[elem]
          self.elements -= 1
          if self.elements > 0:
             SCREAMING_SNAKE_CASE_     =	self.heap[0]
             self._bubble_down(__UpperCAmelCase     )
          return elem



       def   _UpperCamelCase     (				self      ,			_A      ,			_A     )							->							None:
          # Update the weight of the given key
          SCREAMING_SNAKE_CASE_     =	self.position_map[elem]
          SCREAMING_SNAKE_CASE_     =	(elem, weight)
          if position > 0:
             SCREAMING_SNAKE_CASE_     =	get_parent_position(__UpperCAmelCase     )
             SCREAMING_SNAKE_CASE_     =	self.heap[parent_position]
             if parent_weight > weight:
                self._bubble_up(__UpperCAmelCase     )
             else:
                self._bubble_down(__UpperCAmelCase     )
          else:
             self._bubble_down(__UpperCAmelCase     )



       def   _UpperCamelCase     (				self      ,			_A     )							->							None:
          # Place a node at the proper position (upward movement) [to be used internally
          # only]
          SCREAMING_SNAKE_CASE_     =	self.position_map[elem]
          if curr_pos == 0:
             return None
          SCREAMING_SNAKE_CASE_     =	get_parent_position(__UpperCAmelCase     )
          SCREAMING_SNAKE_CASE_     =	self.heap[curr_pos]
          SCREAMING_SNAKE_CASE_     =	self.heap[parent_position]
          if parent_weight > weight:
             self._swap_nodes(__UpperCAmelCase      ,			__UpperCAmelCase     )
             return self._bubble_up(__UpperCAmelCase     )
          return None



       def   _UpperCamelCase     (				self      ,			_A     )							->							None:
          # Place a node at the proper position (downward movement) [to be used
          # internally only]
          SCREAMING_SNAKE_CASE_     =	self.position_map[elem]
          SCREAMING_SNAKE_CASE_     =	self.heap[curr_pos]
          SCREAMING_SNAKE_CASE_     =	get_child_left_position(__UpperCAmelCase     )
          SCREAMING_SNAKE_CASE_     =	get_child_right_position(__UpperCAmelCase     )
          if child_left_position < self.elements and child_right_position < self.elements:
             SCREAMING_SNAKE_CASE_     =	self.heap[child_left_position]
             SCREAMING_SNAKE_CASE_     =	self.heap[child_right_position]
             if child_right_weight < child_left_weight and child_right_weight < weight:
                self._swap_nodes(__UpperCAmelCase      ,			__UpperCAmelCase     )
                return self._bubble_down(__UpperCAmelCase     )
          if child_left_position < self.elements:
             SCREAMING_SNAKE_CASE_     =	self.heap[child_left_position]
             if child_left_weight < weight:
                self._swap_nodes(__UpperCAmelCase      ,			__UpperCAmelCase     )
                return self._bubble_down(__UpperCAmelCase     )
          else:
             return None
          if child_right_position < self.elements:
             SCREAMING_SNAKE_CASE_     =	self.heap[child_right_position]
             if child_right_weight < weight:
                self._swap_nodes(__UpperCAmelCase      ,			__UpperCAmelCase     )
                return self._bubble_down(__UpperCAmelCase     )
          return None




       def   _UpperCamelCase     (				self      ,			_A      ,			_A     )							->							None:
          # Swap the nodes at the given positions
          SCREAMING_SNAKE_CASE_     =	self.heap[nodea_pos][0]
          SCREAMING_SNAKE_CASE_     =	self.heap[nodea_pos][0]
          SCREAMING_SNAKE_CASE_     =	(
              self.heap[nodea_pos],
              self.heap[nodea_pos],
          )
          SCREAMING_SNAKE_CASE_     =	nodea_pos
          SCREAMING_SNAKE_CASE_     =	nodea_pos







class 							UpperCamelCase__						(     Generic[T]     ):






       """simple docstring"""


       def __init__(				self     )							->							None:
          SCREAMING_SNAKE_CASE_     =	{}
          SCREAMING_SNAKE_CASE_     =	0



       def __repr__(				self     )							->							str:
          return str(self.connections     )



       def __len__(				self     )							->							int:
          return self.nodes



       def   _UpperCamelCase     (				self      ,			_A     )							->							None:
          # Add a node in the graph if it is not in the graph
          if node not in self.connections:
             SCREAMING_SNAKE_CASE_     =	{}
             self.nodes += 1




       def   _UpperCamelCase     (				self      ,			_A      ,			_A      ,			_A     )							->							None:
          # Add an edge between 2 nodes in the graph
          self.add_node(__UpperCAmelCase     )
          self.add_node(__UpperCAmelCase     )
          SCREAMING_SNAKE_CASE_     =	weight
          SCREAMING_SNAKE_CASE_     =	weight







def       A__      (    __lowerCamelCase,   ):
   SCREAMING_SNAKE_CASE_     =	{node: maxsize for node in graph.connections}
   SCREAMING_SNAKE_CASE_     =	{node: None for node in graph.connections}

   SCREAMING_SNAKE_CASE_     =	MinPriorityQueue()
   for node, weight in dist.items():
      priority_queue.push(__lowerCamelCase,   __lowerCamelCase		)

   if priority_queue.is_empty():
      return dist, parent

   # initialization
   SCREAMING_SNAKE_CASE_     =	priority_queue.extract_min()
   SCREAMING_SNAKE_CASE_     =	0
   for neighbour in graph.connections[node]:
      if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
         SCREAMING_SNAKE_CASE_     =	dist[node] + graph.connections[node][neighbour]
         priority_queue.update_key(__lowerCamelCase,   dist[neighbour]		)
         SCREAMING_SNAKE_CASE_     =	node

    # running prim's algorithm
   while not priority_queue.is_empty():
      SCREAMING_SNAKE_CASE_     =	priority_queue.extract_min()
      for neighbour in graph.connections[node]:
         if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
            SCREAMING_SNAKE_CASE_     =	dist[node] + graph.connections[node][neighbour]
            priority_queue.update_key(__lowerCamelCase,   dist[neighbour]		)
            SCREAMING_SNAKE_CASE_     =	node
   return dist, parent







'''simple docstring'''





def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    lowerCAmelCase__ :  Tuple							      =					abs(UpperCamelCase			)
    lowerCAmelCase__ :  List[Any]							      =					0
    while n > 0:
        res += n % 10
        n //= 10
    return res
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    lowerCAmelCase__ :  Union[str, Any]							      =					abs(UpperCamelCase			)
    return n if n < 10 else n % 10 + sum_of_digits(n // 10			)
def    _SCREAMING_SNAKE_CASE  (       UpperCamelCase			):



    """simple docstring"""





    return sum(int(UpperCamelCase			) for c in str(abs(UpperCamelCase			)			)			)
def    _SCREAMING_SNAKE_CASE  (       ):



    """simple docstring"""





    from collections.abc import Callable
    from timeit import timeit

    def benchmark_a_function(UpperCamelCase							,    UpperCamelCase			) -> None:
        lowerCAmelCase__ :  str							      =					f"""{func.__name__}({value})"""
        lowerCAmelCase__ :  str							      =					timeit(f"""__main__.{call}"""							,    setup="""import __main__"""			)
        print(f"""{call:56} = {func(UpperCamelCase			)} -- {timing:.4f} seconds"""			)

    for value in (262144, 1125899906842624, 1267650600228229401496703205376):
        for func in (sum_of_digits, sum_of_digits_recursion, sum_of_digits_compact):
            benchmark_a_function(UpperCamelCase							,    UpperCamelCase			)
        print()


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 benchmark()


