




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowercase__				:      Tuple	   = TypeVar("KT")
lowercase__				:      str	   = TypeVar("VT")




class       a__	( Generic[KT, VT]				):







     def __init__(     self  ,		A = "root"  ,		A = None			)  ->   Optional[int]:



          '''simple docstring'''



          a     =				key
          a     =				value
          a     =				[]







     def __repr__(     self			)  ->   str:



          '''simple docstring'''



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







     @property
     def       lowerCAmelCase_    (     self			)  ->   int:



          '''simple docstring'''



          return len(self.forward			)







class       a__	( Generic[KT, VT]				):







     def __init__(     self  ,		A = 0.5  ,		A = 16			)  ->   int:



          '''simple docstring'''



          a     =				Node[KT, VT]()
          a     =				0
          a     =				p
          a     =				max_level







     def __str__(     self			)  ->   str:



          '''simple docstring'''



          a     =				list(self			)

          if len(A			) == 0:
               return F'''SkipList(level={self.level})'''

          a     =				max((len(str(A			)			) for item in items)  ,		default=4			)
          a     =				max(A  ,		4			) + 4

          a     =				self.head
          a     =				[]

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

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

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

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







     def __iter__(     self			)  ->   Optional[int]:



          '''simple docstring'''



          a     =				self.head

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







     def       lowerCAmelCase_    (     self			)  ->   int:



          '''simple docstring'''



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

          return level







     def       lowerCAmelCase_    (     self  ,		A			)  ->   tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:



          '''simple docstring'''



          a     =				[]

          a     =				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:
                    a     =				node.forward[i]
               # Each leftmost node (relative to searched node) will potentially have to
               # be updated.
               update_vector.append(A			)

          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       lowerCAmelCase_    (     self  ,		A			)  ->   List[Any]:



          '''simple docstring'''



          a  ,				a     =				self._locate_node(A			)

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







     def       lowerCAmelCase_    (     self  ,		A  ,		A			)  ->   str:



          '''simple docstring'''



          a  ,				a     =				self._locate_node(A			)
          if node is not None:
               a     =				value
          else:
               a     =				self.random_level()

               if level > self.level:
                    # After level increase we have to add additional nodes to head.
                    for _ in range(self.level - 1  ,		A			):
                         update_vector.append(self.head			)
                    a     =				level

               a     =				Node(A  ,		A			)

               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(A			)
                    else:
                         a     =				new_node







     def       lowerCAmelCase_    (     self  ,		A			)  ->   VT | None:



          '''simple docstring'''



          a  ,				a     =				self._locate_node(A			)

          if node is not None:
               return node.value

          return None







def  SCREAMING_SNAKE_CASE							(       )      ->					Dict:
     a     =				SkipList()
     skip_list.insert("Key1"		, 3)
     skip_list.insert("Key2"		, 12)
     skip_list.insert("Key3"		, 41)
     skip_list.insert("Key4"		, -19)

     a     =				skip_list.head
     a     =				{}
     while node.level != 0:
          a     =				node.forward[0]
          a     =				node.value

     assert len(__UpperCamelCase) == 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							(       )      ->					Optional[Any]:
     a     =				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)

     a     =				skip_list.head
     a     =				{}
     while node.level != 0:
          a     =				node.forward[0]
          a     =				node.value

     if len(__UpperCamelCase) != 4:
          print()
     assert len(__UpperCamelCase) == 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							(       )      ->					List[Any]:
     a     =				SkipList()
     assert skip_list.find("Some key") is None

def  SCREAMING_SNAKE_CASE							(       )      ->					int:
     a     =				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							(       )      ->					Optional[Any]:
     a     =				SkipList()
     skip_list.delete("Some key")

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

def  SCREAMING_SNAKE_CASE							(       )      ->					List[str]:
     a     =				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							(       )      ->					str:
     a     =				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							(       )      ->					str:
     a     =				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(__UpperCamelCase):
          yield node.key
          for forward_node in node.forward:
               yield from traverse_keys(__UpperCamelCase)

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

def  SCREAMING_SNAKE_CASE							(       )      ->					Union[str, Any]:
     def is_sorted(__UpperCamelCase):
          return all(next_item >= item for item, next_item in zip(__UpperCamelCase		, lst[1:]))

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

def  SCREAMING_SNAKE_CASE							(       )      ->					Union[str, Any]:
     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							(       )      ->					int:
     a     =				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(__UpperCamelCase)


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   main()











def  SCREAMING_SNAKE_CASE							(       __UpperCamelCase)      ->					int:
     return 1 if digit in (0, 1) else (digit * factorial(digit - 1))

def  SCREAMING_SNAKE_CASE							(       __UpperCamelCase)      ->					bool:
     a     =				0
     a     =				number
     while duplicate > 0:
          a  ,				a     =				divmod(__UpperCamelCase		, 10)
          fact_sum += factorial(__UpperCamelCase)
     return fact_sum == number


if __name__ == "__main__":
   print("Program to check whether a number is a Krisnamurthy Number or not.")
   lowercase__				:      str	   = int(input("Enter number: ").strip())
   print(
       F'{number} is {"" if krishnamurthy(number) else "not "}a Krishnamurthy Number.'
   )

