




"""simple docstring"""


from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

_A													=      TypeVar("""T""")



def 	lowercase_				(			__UpperCAmelCase				)						->    int:






      """simple docstring"""




      return (position - 1) // 2



def 	lowercase_				(			__UpperCAmelCase				)						->    int:






      """simple docstring"""




      return (2 * position) + 1



def 	lowercase_				(			__UpperCAmelCase				)						->    int:






      """simple docstring"""




      return (2 * position) + 2


class _lowerCamelCase    (					Generic[T]						):






   def __init__(		self       :		Dict   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			list[tuple[T, int]]   =	[]
         lowerCAmelCase__      :			dict[T, int]   =	{}
         lowerCAmelCase__      :			int   =	0






   def __len__(		self       :		Optional[Any]   )			->						int:

         """simple docstring"""
         return self.elements






   def __repr__(		self       :		Any   )			->						str:

         """simple docstring"""
         return str(self.heap   )






   def 	_lowerCAmelCase   (		self       :		List[Any]   )			->						bool:

         """simple docstring"""
         return self.elements == 0






   def 	_lowerCAmelCase   (		self       :		Optional[Any]   ,     UpperCamelCase       :		T   ,     UpperCamelCase       :		int   )			->						None:

         """simple docstring"""
         self.heap.append((elem, weight)   )
         lowerCAmelCase__      :			Dict   =	self.elements
         self.elements += 1
         self._bubble_up(UpperCamelCase   )






   def 	_lowerCAmelCase   (		self       :		List[str]   )			->						T:

         """simple docstring"""
         # Remove and return the element with lowest weight (highest priority)
         if self.elements > 1:
               self._swap_nodes(0   ,     self.elements - 1   )
         lowerCAmelCase__      :			List[Any]   =	self.heap.pop()
         del self.position_map[elem]
         self.elements -= 1
         if self.elements > 0:
               lowerCAmelCase__      :			Optional[Any]   =	self.heap[0]
               self._bubble_down(UpperCamelCase   )
         return elem






   def 	_lowerCAmelCase   (		self       :		List[Any]   ,     UpperCamelCase       :		T   ,     UpperCamelCase       :		int   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			List[Any]   =	self.position_map[elem]
         lowerCAmelCase__      :			Optional[Any]   =	(elem, weight)
         if position > 0:
               lowerCAmelCase__      :			Optional[int]   =	get_parent_position(UpperCamelCase   )
               lowerCAmelCase__      :			Dict   =	self.heap[parent_position]
               if parent_weight > weight:
                     self._bubble_up(UpperCamelCase   )
               else:
                     self._bubble_down(UpperCamelCase   )
         else:
               self._bubble_down(UpperCamelCase   )






   def 	_lowerCAmelCase   (		self       :		Tuple   ,     UpperCamelCase       :		T   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			Optional[int]   =	self.position_map[elem]
         if curr_pos == 0:
               return None
         lowerCAmelCase__      :			Optional[Any]   =	get_parent_position(UpperCamelCase   )
         lowerCAmelCase__      :			Any   =	self.heap[curr_pos]
         lowerCAmelCase__      :			Optional[int]   =	self.heap[parent_position]
         if parent_weight > weight:
               self._swap_nodes(UpperCamelCase   ,     UpperCamelCase   )
               return self._bubble_up(UpperCamelCase   )
         return None






   def 	_lowerCAmelCase   (		self       :		Any   ,     UpperCamelCase       :		T   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			int   =	self.position_map[elem]
         lowerCAmelCase__      :			Dict   =	self.heap[curr_pos]
         lowerCAmelCase__      :			Union[str, Any]   =	get_child_left_position(UpperCamelCase   )
         lowerCAmelCase__      :			Optional[int]   =	get_child_right_position(UpperCamelCase   )
         if child_left_position < self.elements and child_right_position < self.elements:
               lowerCAmelCase__      :			List[Any]   =	self.heap[child_left_position]
               lowerCAmelCase__      :			Dict   =	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:
               lowerCAmelCase__      :			List[Any]   =	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:
               lowerCAmelCase__      :			Tuple   =	self.heap[child_right_position]
               if child_right_weight < weight:
                     self._swap_nodes(UpperCamelCase   ,     UpperCamelCase   )
                     return self._bubble_down(UpperCamelCase   )
         return None






   def 	_lowerCAmelCase   (		self       :		Union[str, Any]   ,     UpperCamelCase       :		int   ,     UpperCamelCase       :		int   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			Dict   =	self.heap[nodea_pos][0]
         lowerCAmelCase__      :			Optional[Any]   =	self.heap[nodea_pos][0]
         lowerCAmelCase__      :			List[Any]   =	(
             self.heap[nodea_pos],
             self.heap[nodea_pos],
         )
         lowerCAmelCase__      :			Tuple   =	nodea_pos
         lowerCAmelCase__      :			Optional[Any]   =	nodea_pos






class _lowerCamelCase    (					Generic[T]						):






   def __init__(		self       :		Dict   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			dict[T, dict[T, int]]   =	{}
         lowerCAmelCase__      :			int   =	0






   def __repr__(		self       :		Any   )			->						str:

         """simple docstring"""
         return str(self.connections   )






   def __len__(		self       :		Tuple   )			->						int:

         """simple docstring"""
         return self.nodes






   def 	_lowerCAmelCase   (		self       :		List[Any]   ,     UpperCamelCase       :		T   )			->						None:

         """simple docstring"""
         # Add a node in the graph if it is not in the graph
         if node not in self.connections:
               lowerCAmelCase__      :			List[str]   =	{}
               self.nodes += 1






   def 	_lowerCAmelCase   (		self       :		Union[str, Any]   ,     UpperCamelCase       :		T   ,     UpperCamelCase       :		T   ,     UpperCamelCase       :		int   )			->						None:

         """simple docstring"""
         self.add_node(UpperCamelCase   )
         self.add_node(UpperCamelCase   )
         lowerCAmelCase__      :			Tuple   =	weight
         lowerCAmelCase__      :			int   =	weight






def 	lowercase_				(			__UpperCAmelCase    ,		)						->    tuple[dict[T, int], dict[T, T | None]]:






      """simple docstring"""




      lowerCAmelCase__      :			dict[T, int]   =	{node: maxsize for node in graph.connections}
      lowerCAmelCase__      :			dict[T, T | None]   =	{node: None for node in graph.connections}

      lowerCAmelCase__      :			MinPriorityQueue[T]   =	MinPriorityQueue()
      for node, weight in dist.items():
            priority_queue.push(__UpperCAmelCase    ,		__UpperCAmelCase				)

      if priority_queue.is_empty():
            return dist, parent

      # initialization
      lowerCAmelCase__      :			Optional[Any]   =	priority_queue.extract_min()
      lowerCAmelCase__      :			Any   =	0
      for neighbour in graph.connections[node]:
            if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
                  lowerCAmelCase__      :			Any   =	dist[node] + graph.connections[node][neighbour]
                  priority_queue.update_key(__UpperCAmelCase    ,		dist[neighbour]				)
                  lowerCAmelCase__      :			List[Any]   =	node

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











"""simple docstring"""


def 	lowercase_				(			__UpperCAmelCase    ,		__UpperCAmelCase				)						->    str:
      return "\n".join(
          f"""{number} * {i} = {number * i}""" for i in range(1    ,		number_of_terms + 1				)				)


if __name__ == "__main__":
  print(multiplication_table(number=5, number_of_terms=1_0))





