
from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

_UpperCAmelCase					: str      =       TypeVar("T")


def       A       (					lowercase )   ->  int:
		'''simple docstring'''

		return (position - 1) // 2


def       A       (					lowercase )   ->  int:
		'''simple docstring'''

		return (2 * position) + 1


def       A       (					lowercase )   ->  int:
		'''simple docstring'''

		return (2 * position) + 2


class 				lowercase					(		Generic[T]   ):



		def __init__( self       )  ->					None:
				"""simple docstring"""
				UpperCamelCase		=     []
				UpperCamelCase		=     {}
				UpperCamelCase		=     0



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



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



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



		def __UpperCamelCase ( self				,      A_				,      A_       )  ->					None:
				"""simple docstring"""
				# Add an element with given priority to the queue
				self.heap.append((elem, weight)       )
				UpperCamelCase		=     self.elements
				self.elements += 1
				self._bubble_up(A_       )



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



		def __UpperCamelCase ( self				,      A_				,      A_       )  ->					None:
				"""simple docstring"""
				# Update the weight of the given key
				UpperCamelCase		=     self.position_map[elem]
				UpperCamelCase		=     (elem, weight)
				if position > 0:
						UpperCamelCase		=     get_parent_position(A_       )
						UpperCamelCase	,  UpperCamelCase		=     self.heap[parent_position]
						if parent_weight > weight:
								self._bubble_up(A_       )
						else:
								self._bubble_down(A_       )
				else:
						self._bubble_down(A_       )



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



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



		def __UpperCamelCase ( self				,      A_				,      A_       )  ->					None:
				"""simple docstring"""
				# Swap the nodes at the given positions
				UpperCamelCase		=     self.heap[nodea_pos][0]
				UpperCamelCase		=     self.heap[nodea_pos][0]
				UpperCamelCase	,  UpperCamelCase		=     (
				    self.heap[nodea_pos],
				    self.heap[nodea_pos],
				)
				UpperCamelCase		=     nodea_pos
				UpperCamelCase		=     nodea_pos






class 				lowercase					(		Generic[T]   ):



		def __init__( self       )  ->					None:
				"""simple docstring"""
				UpperCamelCase		=     {}
				UpperCamelCase		=     0



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



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



		def __UpperCamelCase ( self				,      A_       )  ->					None:
				"""simple docstring"""
				# Add a node in the graph if it is not in the graph
				if node not in self.connections:
						UpperCamelCase		=     {}
						self.nodes += 1



		def __UpperCamelCase ( self				,      A_				,      A_				,      A_       )  ->					None:
				"""simple docstring"""
				# Add an edge between 2 nodes in the graph
				self.add_node(A_       )
				self.add_node(A_       )
				UpperCamelCase		=     weight
				UpperCamelCase		=     weight






def       A       (					lowercase    ,       )   ->  tuple[dict[T, int], dict[T, T | None]]:
		'''simple docstring'''

		UpperCamelCase		=     {node: maxsize for node in graph.connections}
		UpperCamelCase		=     {node: None for node in graph.connections}

		UpperCamelCase		=     MinPriorityQueue()
		for node, weight in dist.items():
				priority_queue.push(lowercase    ,       lowercase )

		if priority_queue.is_empty():
				return dist, parent

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

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


from decimal import Decimal, getcontext
from math import ceil, factorial


def       A       (					lowercase )   ->  str:
		'''simple docstring'''

		if not isinstance(lowercase    ,       lowercase ):
				raise TypeError('Undefined for non-integers' )
		elif precision < 1:
				raise ValueError('Undefined for non-natural numbers' )

		UpperCamelCase		=     precision
		UpperCamelCase		=     ceil(precision / 14 )
		UpperCamelCase		=     426_880 * Decimal(10_005 ).sqrt()
		UpperCamelCase		=     1
		UpperCamelCase		=     13_591_409
		UpperCamelCase		=     Decimal(lowercase )
		for k in range(1    ,       lowercase ):
				UpperCamelCase		=     factorial(6 * k ) // (factorial(3 * k ) * factorial(lowercase ) ** 3)
				linear_term += 545_140_134
				exponential_term *= -262_537_412_640_768_000
				partial_sum += Decimal(multinomial_term * linear_term ) / exponential_term
		return str(constant_term / partial_sum )[:-1]


if __name__ == "__main__":
					_UpperCAmelCase					: Dict      =       50
					print(F'''The first {n} digits of pi is: {pi(n)}''')
