





from __future__ import annotations

from random import random
from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE							=						TypeVar("""KT""")
_SCREAMING_SNAKE_CASE							=						TypeVar("""VT""")
class SCREAMING_SNAKE_CASE_  (    Generic[KT, VT]    ):






						def __init__(					self					:					Union[str, Any]						,      _A					:					List[str] = "root"						,      _A					:					Dict = None		)							->			Tuple:







							"""simple docstring"""


							snake_case_						:	Union[str, Any]      =		key
							snake_case_						:	List[Any]      =		value
							snake_case_						:	int      =		[]






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







							"""simple docstring"""


							return F"""Node({self.key}: {self.value})"""






						@property
						def UpperCAmelCase_ (					self					:					Optional[int]		)							->			str:







							"""simple docstring"""


							return len(self.forward		)
class SCREAMING_SNAKE_CASE_  (    Generic[KT, VT]    ):






						def __init__(					self					:					str						,      _A					:					Dict = 0.5						,      _A					:					str = 16		)							->			int:







							"""simple docstring"""


							snake_case_						:	List[str]      =		Node[KT, VT]()
							snake_case_						:	Any      =		0
							snake_case_						:	Tuple      =		p
							snake_case_						:	Union[str, Any]      =		max_level






						def __str__(					self					:					int		)							->			int:







							"""simple docstring"""


							snake_case_						:	Tuple      =		list(self		)

							if len(__lowerCAmelCase		) == 0:
								return F"""SkipList(level={self.level})"""

							snake_case_						:	int      =		max((len(str(__lowerCAmelCase		)		) for item in items)						,      default=4		)
							snake_case_						:	Union[str, Any]      =		max(__lowerCAmelCase						,      4		) + 4

							snake_case_						:	Tuple      =		self.head
							snake_case_						:	Optional[Any]      =		[]

							snake_case_						:	Dict      =		node.forward.copy()
							lines.append(F"""[{node.key}]""".ljust(__lowerCAmelCase						,      '-'		) + '* ' * len(__lowerCAmelCase		)		)
							lines.append(' ' * label_size + '| ' * len(__lowerCAmelCase		)		)

							while len(node.forward		) != 0:
								snake_case_						:	Dict      =		node.forward[0]

								lines.append(
								    F"""[{node.key}]""".ljust(__lowerCAmelCase						,      '-'		)
								    + ' '.join(str(n.key		) if n.key == node.key else '|' for n in forwards		)		)
								lines.append(' ' * label_size + '| ' * len(__lowerCAmelCase		)		)
								snake_case_						:	Optional[Any]      =		node.forward

							lines.append('None'.ljust(__lowerCAmelCase		) + '* ' * len(__lowerCAmelCase		)		)
							return F"""SkipList(level={self.level})\n""" + "\n".join(__lowerCAmelCase		)






						def __iter__(					self					:					Any		)							->			Dict:







							"""simple docstring"""


							snake_case_						:	Tuple      =		self.head

							while len(node.forward		) != 0:
								yield node.forward[0].key
								snake_case_						:	int      =		node.forward[0]






						def UpperCAmelCase_ (					self					:					Union[str, Any]		)							->			Union[str, Any]:







							"""simple docstring"""


							snake_case_						:	Tuple      =		1
							while random() < self.p and level < self.max_level:
								level += 1

							return level






						def UpperCAmelCase_ (					self					:					Optional[Any]						,      _A					:					List[Any]		)							->			Optional[Any]:







							"""simple docstring"""


							snake_case_						:	Any      =		[]

							snake_case_						:	Tuple      =		self.head

							for i in reversed(range(self.level		)		):
								# i < node.level - When node level is lesser than `i` decrement `i`.
								# node.forward[i].key < key - Jumping to node with key value higher
								#                             or equal to searched key would result
								#                             in skipping searched key.
								while i < node.level and node.forward[i].key < key:
									snake_case_						:	int      =		node.forward[i]
								# Each leftmost node (relative to searched node) will potentially have to
								# be updated.
								update_vector.append(__lowerCAmelCase		)

							update_vector.reverse()  # Note that we were inserting values in reverse order.

							# len(node.forward) != 0 - If current node doesn't contain any further
							#                          references then searched key is not present.
							# node.forward[0].key == key - Next node key should be equal to search key
							#                              if key is present.
							if len(node.forward		) != 0 and node.forward[0].key == key:
								return node.forward[0], update_vector
							else:
								return None, update_vector






						def UpperCAmelCase_ (					self					:					List[str]						,      _A					:					Any		)							->			Optional[Any]:







							"""simple docstring"""


							snake_case_  ,snake_case_						:	Dict      =		self._locate_node(__lowerCAmelCase		)

							if node is not None:
								for i, update_node in enumerate(__lowerCAmelCase		):
									# Remove or replace all references to removed node.
									if update_node.level > i and update_node.forward[i].key == key:
										if node.level > i:
											snake_case_						:	List[Any]      =		node.forward[i]
										else:
											snake_case_						:	Dict      =		update_node.forward[:i]






						def UpperCAmelCase_ (					self					:					Optional[int]						,      _A					:					Any						,      _A					:					Tuple		)							->			List[Any]:







							"""simple docstring"""


							snake_case_  ,snake_case_						:	List[Any]      =		self._locate_node(__lowerCAmelCase		)
							if node is not None:
								snake_case_						:	Optional[Any]      =		value
							else:
								snake_case_						:	str      =		self.random_level()

								if level > self.level:
									# After level increase we have to add additional nodes to head.
									for _ in range(self.level - 1						,      __lowerCAmelCase		):
										update_vector.append(self.head		)
									snake_case_						:	Optional[int]      =		level

								snake_case_						:	int      =		Node(__lowerCAmelCase						,      __lowerCAmelCase		)

								for i, update_node in enumerate(update_vector[:level]		):
									# Change references to pass through new node.
									if update_node.level > i:
										new_node.forward.append(update_node.forward[i]		)

									if update_node.level < i + 1:
										update_node.forward.append(__lowerCAmelCase		)
									else:
										snake_case_						:	Union[str, Any]      =		new_node






						def UpperCAmelCase_ (					self					:					str						,      _A					:					Tuple		)							->			List[Any]:







							"""simple docstring"""


							snake_case_  ,snake_case_						:	Tuple      =		self._locate_node(__lowerCAmelCase		)

							if node is not None:
								return node.value

							return None


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Any      =		SkipList()
	skip_list.insert('Key1'      ,       3      )
	skip_list.insert('Key2'      ,       12      )
	skip_list.insert('Key3'      ,       41      )
	skip_list.insert('Key4'      ,       -19      )

	snake_case_						:	int      =		skip_list.head
	snake_case_						:	List[str]      =		{}
	while node.level != 0:
		snake_case_						:	List[str]      =		node.forward[0]
		snake_case_						:	str      =		node.value

	assert len(lowerCAmelCase__      ) == 4
	assert all_values["Key1"] == 3
	assert all_values["Key2"] == 12
	assert all_values["Key3"] == 41
	assert all_values["Key4"] == -19


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Dict      =		SkipList()
	skip_list.insert('Key1'      ,       10      )
	skip_list.insert('Key1'      ,       12      )

	skip_list.insert('Key5'      ,       7      )
	skip_list.insert('Key7'      ,       10      )
	skip_list.insert('Key10'      ,       5      )

	skip_list.insert('Key7'      ,       7      )
	skip_list.insert('Key5'      ,       5      )
	skip_list.insert('Key10'      ,       10      )

	snake_case_						:	Dict      =		skip_list.head
	snake_case_						:	Optional[int]      =		{}
	while node.level != 0:
		snake_case_						:	Union[str, Any]      =		node.forward[0]
		snake_case_						:	Union[str, Any]      =		node.value

	if len(lowerCAmelCase__      ) != 4:
		print()
	assert len(lowerCAmelCase__      ) == 4
	assert all_values["Key1"] == 12
	assert all_values["Key7"] == 7
	assert all_values["Key5"] == 5
	assert all_values["Key10"] == 10


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Any      =		SkipList()
	assert skip_list.find('Some key'      ) is None


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	List[Any]      =		SkipList()

	skip_list.insert('Key2'      ,       20      )
	assert skip_list.find('Key2'      ) == 20

	skip_list.insert('Some Key'      ,       10      )
	skip_list.insert('Key2'      ,       8      )
	skip_list.insert('V'      ,       13      )

	assert skip_list.find('Y'      ) is None
	assert skip_list.find('Key2'      ) == 8
	assert skip_list.find('Some Key'      ) == 10
	assert skip_list.find('V'      ) == 13


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Optional[int]      =		SkipList()
	skip_list.delete('Some key'      )

	assert len(skip_list.head.forward      ) == 0


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	int      =		SkipList()

	skip_list.insert('Key1'      ,       12      )
	skip_list.insert('V'      ,       13      )
	skip_list.insert('X'      ,       14      )
	skip_list.insert('Key2'      ,       15      )

	skip_list.delete('V'      )
	skip_list.delete('Key2'      )

	assert skip_list.find('V'      ) is None
	assert skip_list.find('Key2'      ) is None


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Tuple      =		SkipList()

	skip_list.insert('Key1'      ,       12      )
	skip_list.insert('V'      ,       13      )
	skip_list.insert('X'      ,       14      )
	skip_list.insert('Key2'      ,       15      )

	skip_list.delete('V'      )
	assert skip_list.find('V'      ) is None
	assert skip_list.find('X'      ) == 14
	assert skip_list.find('Key1'      ) == 12
	assert skip_list.find('Key2'      ) == 15

	skip_list.delete('X'      )
	assert skip_list.find('V'      ) is None
	assert skip_list.find('X'      ) is None
	assert skip_list.find('Key1'      ) == 12
	assert skip_list.find('Key2'      ) == 15

	skip_list.delete('Key1'      )
	assert skip_list.find('V'      ) is None
	assert skip_list.find('X'      ) is None
	assert skip_list.find('Key1'      ) is None
	assert skip_list.find('Key2'      ) == 15

	skip_list.delete('Key2'      )
	assert skip_list.find('V'      ) is None
	assert skip_list.find('X'      ) is None
	assert skip_list.find('Key1'      ) is None
	assert skip_list.find('Key2'      ) is None


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Any      =		SkipList()

	skip_list.insert('Key1'      ,       12      )
	skip_list.insert('V'      ,       13      )
	skip_list.insert('X'      ,       1_42      )
	skip_list.insert('Key2'      ,       15      )

	skip_list.delete('X'      )

	def traverse_keys(__a      ):
		yield node.key
		for forward_node in node.forward:
			yield from traverse_keys(lowerCAmelCase__      )

	assert len(set(traverse_keys(skip_list.head      )      )      ) == 4


def 							SCREAMING_SNAKE_CASE__  (			):


	def is_sorted(__a      ):
		return all(next_item >= item for item, next_item in zip(lowerCAmelCase__      ,       lst[1:]      )      )

	snake_case_						:	str      =		SkipList()
	for i in range(10      ):
		skip_list.insert(lowerCAmelCase__      ,       lowerCAmelCase__      )
	assert is_sorted(list(lowerCAmelCase__      )      )
	skip_list.delete(5      )
	skip_list.delete(8      )
	skip_list.delete(2      )
	assert is_sorted(list(lowerCAmelCase__      )      )
	skip_list.insert(-12      ,       -12      )
	skip_list.insert(77      ,       77      )
	assert is_sorted(list(lowerCAmelCase__      )      )


def 							SCREAMING_SNAKE_CASE__  (			):


	for _ in range(1_00      ):
		# Repeat test 100 times due to the probabilistic nature of skip list
		# random values == random bugs
		test_insert()
		test_insert_overrides_existing_value()

		test_searching_empty_list_returns_none()
		test_search()

		test_deleting_item_from_empty_list_do_nothing()
		test_deleted_items_are_not_founded_by_find_method()
		test_delete_removes_only_given_key()
		test_delete_doesnt_leave_dead_nodes()

		test_iter_always_yields_sorted_values()


def 							SCREAMING_SNAKE_CASE__  (			):
	snake_case_						:	Tuple      =		SkipList()
	skip_list.insert(2      ,       '2'      )
	skip_list.insert(4      ,       '4'      )
	skip_list.insert(6      ,       '4'      )
	skip_list.insert(4      ,       '5'      )
	skip_list.insert(8      ,       '4'      )
	skip_list.insert(9      ,       '4'      )

	skip_list.delete(4      )

	print(lowerCAmelCase__      )


if __name__ == "__main__":
						import doctest

						doctest.testmod()
						main()


"""simple docstring"""






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


def 			UpperCAmelCase__       (				lowerCAmelCase__     :int		) ->    str:
      '''simple docstring'''


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

      lowercase														=	precision
      lowercase														=	ceil(precision / 1_4		)
      lowercase														=	4_2_6_8_8_0 * Decimal(1_0_0_0_5		).sqrt()
      lowercase														=	1
      lowercase														=	1_3_5_9_1_4_0_9
      lowercase														=	Decimal(lowerCAmelCase__		)
      for k in range(1					,		lowerCAmelCase__		):
            lowercase														=	factorial(6 * k		) // (factorial(3 * k		) * factorial(lowerCAmelCase__		) ** 3)
            linear_term += 5_4_5_1_4_0_1_3_4
            exponential_term *= -2_6_2_5_3_7_4_1_2_6_4_0_7_6_8_0_0_0
            partial_sum += Decimal(multinomial_term * linear_term		) / exponential_term
      return str(constant_term / partial_sum		)[:-1]


if __name__ == "__main__":
       __lowerCAmelCase    :       List[Any]					     =5_0
       print(F"""The first {n} digits of pi is: {pi(n)}""")



