from __future__ import annotations

from random import random
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE__		:       List[str]       						=       TypeVar("KT")
SCREAMING_SNAKE_CASE__		:       str       						=       TypeVar("VT")

class    snake_case       (   Generic[KT, VT]    ):




  def __init__(   self  :						Union[str, Any]  ,			a_  :						KT | str = "root"  ,			a_  :						VT | None = None					)->							Optional[Any]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__					:					Optional[int]      =		key
       SCREAMING_SNAKE_CASE__					:					Dict      =		value
       SCREAMING_SNAKE_CASE__					:					list[Node[KT, VT]]      =		[]




  def __repr__(   self  :						Dict					)->							str:




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




  @property
  def 						__lowercase(   self  :						List[str]					)->							int:




       """simple docstring"""
       return len(self.forward					)




class    snake_case       (   Generic[KT, VT]    ):




  def __init__(   self  :						Union[str, Any]  ,			a_  :						float = 0.5  ,			a_  :						int = 16					)->							List[Any]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__					:					Node[KT, VT]      =		Node[KT, VT]()
       SCREAMING_SNAKE_CASE__					:					Tuple      =		0
       SCREAMING_SNAKE_CASE__					:					str      =		p
       SCREAMING_SNAKE_CASE__					:					Optional[int]      =		max_level




  def __str__(   self  :						Optional[Any]					)->							str:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__					:					Dict      =		list(self					)

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

       SCREAMING_SNAKE_CASE__					:					str      =		max((len(str(a_					)					) for item in items)  ,			default=4					)
       SCREAMING_SNAKE_CASE__					:					Dict      =		max(a_  ,			4					) + 4

       SCREAMING_SNAKE_CASE__					:					Dict      =		self.head
       SCREAMING_SNAKE_CASE__					:					Union[str, Any]      =		[]

       SCREAMING_SNAKE_CASE__					:					int      =		node.forward.copy()
       lines.append(F'''[{node.key}]'''.ljust(a_  ,			'-'					) + '* ' * len(a_					)					)
       lines.append(' ' * label_size + '| ' * len(a_					)					)

       while len(node.forward					) != 0:
            SCREAMING_SNAKE_CASE__					:					int      =		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_					)					)
            SCREAMING_SNAKE_CASE__					:					Optional[int]      =		node.forward

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




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




       """simple docstring"""
       SCREAMING_SNAKE_CASE__					:					Tuple      =		self.head

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




  def 						__lowercase(   self  :						str					)->							int:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__					:					List[str]      =		1
       while random() < self.p and level < self.max_level:
            level += 1

       return level




  def 						__lowercase(   self  :						Dict  ,			a_  :						Optional[int]					)->							tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__					:					int      =		[]

       SCREAMING_SNAKE_CASE__					:					Any      =		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:
                 SCREAMING_SNAKE_CASE__					:					str      =		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 						__lowercase(   self  :						Optional[Any]  ,			a_  :						KT					)->							Dict:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__      ,				SCREAMING_SNAKE_CASE__					:					Union[str, Any]      =		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:
                           SCREAMING_SNAKE_CASE__					:					List[Any]      =		node.forward[i]
                      else:
                           SCREAMING_SNAKE_CASE__					:					Optional[Any]      =		update_node.forward[:i]




  def 						__lowercase(   self  :						Any  ,			a_  :						KT  ,			a_  :						VT					)->							List[str]:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__      ,				SCREAMING_SNAKE_CASE__					:					str      =		self._locate_node(a_					)
       if node is not None:
            SCREAMING_SNAKE_CASE__					:					str      =		value
       else:
            SCREAMING_SNAKE_CASE__					:					Dict      =		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					)
                 SCREAMING_SNAKE_CASE__					:					List[Any]      =		level

            SCREAMING_SNAKE_CASE__					:					Union[str, Any]      =		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:
                      SCREAMING_SNAKE_CASE__					:					Optional[int]      =		new_node




  def 						__lowercase(   self  :						Any  ,			a_  :						VT					)->							VT | None:




       """simple docstring"""
       SCREAMING_SNAKE_CASE__      ,				SCREAMING_SNAKE_CASE__					:					int      =		self._locate_node(a_					)

       if node is not None:
            return node.value

       return None







def      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					Optional[int]      =		SkipList()
     skip_list.insert('Key1'  ,	3			)
     skip_list.insert('Key2'  ,	12			)
     skip_list.insert('Key3'  ,	41			)
     skip_list.insert('Key4'  ,	-19			)

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

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







def      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					List[str]      =		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			)

     SCREAMING_SNAKE_CASE__					:					Dict      =		skip_list.head
     SCREAMING_SNAKE_CASE__					:					Any      =		{}
     while node.level != 0:
          SCREAMING_SNAKE_CASE__					:					int      =		node.forward[0]
          SCREAMING_SNAKE_CASE__					:					List[Any]      =		node.value

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







def      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					str      =		SkipList()
     assert skip_list.find('Some key'			) is None







def      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					Optional[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      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					Any      =		SkipList()
     skip_list.delete('Some key'			)

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







def      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					List[Any]      =		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      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					Dict      =		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      _a					(   ):







     '''simple docstring'''


     SCREAMING_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(lowercase__	:      Any			):
          yield node.key
          for forward_node in node.forward:
               yield from traverse_keys(lowercase__			)

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







def      _a					(   ):







     '''simple docstring'''


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

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







def      _a					(   ):







     '''simple docstring'''


     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      _a					(   ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__					:					Optional[Any]      =		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(lowercase__			)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      main()











'''simple docstring'''





_UpperCamelCase						:						Dict  =					range(2, 20 + 1)
_UpperCamelCase						:						str  =					[10**k for k in range(ks[-1] + 1)]
_UpperCamelCase						:						dict[int, dict[int, list[list[int]]]]  =					{}
def __UpperCAmelCase   (					A					:			List[Any]			,       A					:			str			,       A					:			Union[str, Any]			,       A					:			Union[str, Any]		)    ->   Optional[Any]:
			UpperCAmelCase_      :       Optional[Any]          =       sum(a_i[j] for j in range(A			,       len(A		)		)		)
			UpperCAmelCase_      :       Union[str, Any]          =       sum(a_i[j] * base[j] for j in range(min(len(A		)			,       A		)		)		)

			UpperCAmelCase_    ,      UpperCAmelCase_      :       Optional[int]          =       0, 0
			UpperCAmelCase_      :       str          =       n - i

			UpperCAmelCase_      :       Union[str, Any]          =       memo.get(A		)

			if sub_memo is not None:
						UpperCAmelCase_      :       Dict          =       sub_memo.get(A		)

						if jumps is not None and len(A		) > 0:
									# find and make the largest jump without going over
									UpperCAmelCase_      :       str          =       -1
									for _k in range(len(A		) - 1			,       -1			,       -1		):
												if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
															UpperCAmelCase_      :       Any          =       _k
															break

									if max_jump >= 0:
												UpperCAmelCase_    ,      UpperCAmelCase_    ,      UpperCAmelCase_      :       Any          =       jumps[max_jump]
												# since the difference between jumps is cached, add c
												UpperCAmelCase_      :       Union[str, Any]          =       diff + c
												for j in range(min(A			,       len(A		)		)		):
															UpperCAmelCase_    ,      UpperCAmelCase_      :       Tuple          =       divmod(A			,       1_0		)
												if new_c > 0:
															add(A			,       A			,       A		)

						else:
									UpperCAmelCase_      :       Tuple          =       []
			else:
						UpperCAmelCase_      :       List[str]          =       {c: []}
						UpperCAmelCase_      :       List[str]          =       sub_memo

			if dn >= max_dn or c + diff >= base[k]:
						return diff, dn

			if k > ks[0]:
						while True:
									# keep doing smaller jumps
									UpperCAmelCase_    ,      UpperCAmelCase_      :       Optional[Any]          =       next_term(A			,       k - 1			,       i + dn			,       A		)
									diff += _diff
									dn += terms_jumped

									if dn >= max_dn or c + diff >= base[k]:
												break
			else:
						# would be too small a jump, just compute sequential terms instead
						UpperCAmelCase_    ,      UpperCAmelCase_      :       int          =       compute(A			,       A			,       i + dn			,       A		)
						diff += _diff
						dn += terms_jumped

			UpperCAmelCase_      :       List[str]          =       sub_memo[c]

			# keep jumps sorted by # of terms skipped
			UpperCAmelCase_      :       List[Any]          =       0
			while j < len(A		):
						if jumps[j][1] > dn:
									break
						j += 1

			# cache the jump for this value digitsum(b) and c
			sub_memo[c].insert(A			,       (diff, dn, k)		)
			return (diff, dn)
def __UpperCAmelCase   (					A					:			List[str]			,       A					:			Dict			,       A					:			List[str]			,       A					:			Union[str, Any]		)    ->   str:
			if i >= n:
						return 0, i
			if k > len(A		):
						a_i.extend([0 for _ in range(k - len(A		)		)]		)

			# note: a_i -> b * 10^k + c
			# ds_b -> digitsum(b)
			# ds_c -> digitsum(c)
			UpperCAmelCase_      :       int          =       i
			UpperCAmelCase_    ,      UpperCAmelCase_    ,      UpperCAmelCase_      :       List[Any]          =       0, 0, 0
			for j in range(len(A		)		):
						if j >= k:
									ds_b += a_i[j]
						else:
									ds_c += a_i[j]

			while i < n:
						i += 1
						UpperCAmelCase_      :       Optional[int]          =       ds_c + ds_b
						diff += addend
						UpperCAmelCase_      :       Any          =       0
						for j in range(A		):
									UpperCAmelCase_      :       Dict          =       a_i[j] + addend
									UpperCAmelCase_    ,      UpperCAmelCase_      :       Tuple          =       divmod(A			,       1_0		)

									ds_c += a_i[j]

						if addend > 0:
									break

			if addend > 0:
						add(A			,       A			,       A		)
			return diff, i - start_i
def __UpperCAmelCase   (					A					:			Dict			,       A					:			Union[str, Any]			,       A					:			str		)    ->   List[Any]:
			for j in range(A			,       len(A		)		):
						UpperCAmelCase_      :       List[str]          =       digits[j] + addend
						if s >= 1_0:
									UpperCAmelCase_    ,      UpperCAmelCase_      :       Any          =       divmod(A			,       1_0		)
									UpperCAmelCase_      :       str          =       addend // 1_0 + quotient
						else:
									UpperCAmelCase_      :       Any          =       s
									UpperCAmelCase_      :       Any          =       addend // 1_0

						if addend == 0:
									break

			while addend > 0:
						UpperCAmelCase_    ,      UpperCAmelCase_      :       Union[str, Any]          =       divmod(A			,       1_0		)
						digits.append(A		)
def __UpperCAmelCase   (					A					:			int = 1_0**1_5		)    ->   int:
			UpperCAmelCase_      :       Any          =       [1]
			UpperCAmelCase_      :       Union[str, Any]          =       1
			UpperCAmelCase_      :       List[Any]          =       0
			while True:
						UpperCAmelCase_    ,      UpperCAmelCase_      :       str          =       next_term(A			,       2_0			,       i + dn			,       A		)
						dn += terms_jumped
						if dn == n - i:
									break

			UpperCAmelCase_      :       Any          =       0
			for j in range(len(A		)		):
						a_n += digits[j] * 1_0**j
			return a_n


if __name__ == "__main__":
						print(f'''{solution() = }''')


