




'''simple docstring'''

from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowercase_     		= TypeVar('''KT''')
lowercase_     		= TypeVar('''VT''')
class   SCREAMING_SNAKE_CASE			(						Generic[KT, VT]):







		"""simple docstring"""






		def __init__(   self		,						__A = "root"		,						__A = None				) ->     int:
								_lowerCAmelCase										=key
								_lowerCAmelCase										=value
								_lowerCAmelCase										=[]






		def __repr__(   self				) ->     Union[str, Any]:
								return F'''Node({self.key}: {self.value})'''






		@property
		def 		UpperCamelCase__       (   self				) ->     Optional[Any]:
								return len(self.forward				)

class   SCREAMING_SNAKE_CASE			(						Generic[KT, VT]):







		"""simple docstring"""






		def __init__(   self		,						__A = 0.5		,						__A = 16				) ->     Tuple:
								_lowerCAmelCase										=Node[KT, VT]()
								_lowerCAmelCase										=0
								_lowerCAmelCase										=p
								_lowerCAmelCase										=max_level






		def __str__(   self				) ->     List[Any]:
								_lowerCAmelCase										=list(self				)

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

								_lowerCAmelCase										=max((len(str(lowerCAmelCase_				)				) for item in items)		,						default=4				)
								_lowerCAmelCase										=max(lowerCAmelCase_		,						4				) + 4

								_lowerCAmelCase										=self.head
								_lowerCAmelCase										=[]

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

								while len(node.forward				) != 0:
														_lowerCAmelCase										=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_				)				)
														_lowerCAmelCase										=node.forward

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






		def __iter__(   self				) ->     Optional[int]:
								_lowerCAmelCase										=self.head

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






		def 		UpperCamelCase__       (   self				) ->     List[Any]:
								_lowerCAmelCase										=1
								while random() < self.p and level < self.max_level:
														level += 1

								return level






		def 		UpperCamelCase__       (   self		,						__A				) ->     List[str]:
								_lowerCAmelCase										=[]

								_lowerCAmelCase										=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:
																				_lowerCAmelCase										=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		,						__A				) ->     List[str]:
								_lowerCAmelCase						,				_lowerCAmelCase										=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:
																																_lowerCAmelCase										=node.forward[i]
																										else:
																																_lowerCAmelCase										=update_node.forward[:i]






		def 		UpperCamelCase__       (   self		,						__A		,						__A				) ->     Dict:
								_lowerCAmelCase						,				_lowerCAmelCase										=self._locate_node(lowerCAmelCase_				)
								if node is not None:
														_lowerCAmelCase										=value
								else:
														_lowerCAmelCase										=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				)
																				_lowerCAmelCase										=level

														_lowerCAmelCase										=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:
																										_lowerCAmelCase										=new_node






		def 		UpperCamelCase__       (   self		,						__A				) ->     Optional[Any]:
								_lowerCAmelCase						,				_lowerCAmelCase										=self._locate_node(lowerCAmelCase_				)

								if node is not None:
														return node.value

								return None



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()
						skip_list.insert('Key1'			,      3      )
						skip_list.insert('Key2'			,      1_2      )
						skip_list.insert('Key3'			,      4_1      )
						skip_list.insert('Key4'			,      -1_9      )

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

						assert len(__lowerCAmelCase      ) == 4
						assert all_values["Key1"] == 3
						assert all_values["Key2"] == 1_2
						assert all_values["Key3"] == 4_1
						assert all_values["Key4"] == -1_9



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()
						skip_list.insert('Key1'			,      1_0      )
						skip_list.insert('Key1'			,      1_2      )

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

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

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

						if len(__lowerCAmelCase      ) != 4:
												print()
						assert len(__lowerCAmelCase      ) == 4
						assert all_values["Key1"] == 1_2
						assert all_values["Key7"] == 7
						assert all_values["Key5"] == 5
						assert all_values["Key10"] == 1_0



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()
						assert skip_list.find('Some key'      ) is None



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()

						skip_list.insert('Key2'			,      2_0      )
						assert skip_list.find('Key2'      ) == 2_0

						skip_list.insert('Some Key'			,      1_0      )
						skip_list.insert('Key2'			,      8      )
						skip_list.insert('V'			,      1_3      )

						assert skip_list.find('Y'      ) is None
						assert skip_list.find('Key2'      ) == 8
						assert skip_list.find('Some Key'      ) == 1_0
						assert skip_list.find('V'      ) == 1_3



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()
						skip_list.delete('Some key'      )

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



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()

						skip_list.insert('Key1'			,      1_2      )
						skip_list.insert('V'			,      1_3      )
						skip_list.insert('X'			,      1_4      )
						skip_list.insert('Key2'			,      1_5      )

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

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



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()

						skip_list.insert('Key1'			,      1_2      )
						skip_list.insert('V'			,      1_3      )
						skip_list.insert('X'			,      1_4      )
						skip_list.insert('Key2'			,      1_5      )

						skip_list.delete('V'      )
						assert skip_list.find('V'      ) is None
						assert skip_list.find('X'      ) == 1_4
						assert skip_list.find('Key1'      ) == 1_2
						assert skip_list.find('Key2'      ) == 1_5

						skip_list.delete('X'      )
						assert skip_list.find('V'      ) is None
						assert skip_list.find('X'      ) is None
						assert skip_list.find('Key1'      ) == 1_2
						assert skip_list.find('Key2'      ) == 1_5

						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'      ) == 1_5

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


						'''simple docstring'''






						_lowerCAmelCase										=SkipList()

						skip_list.insert('Key1'			,      1_2      )
						skip_list.insert('V'			,      1_3      )
						skip_list.insert('X'			,      1_4_2      )
						skip_list.insert('Key2'			,      1_5      )

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


						'''simple docstring'''






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

						_lowerCAmelCase										=SkipList()
						for i in range(1_0      ):
												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(-1_2			,      -1_2      )
						skip_list.insert(7_7			,      7_7      )
						assert is_sorted(list(__lowerCAmelCase      )      )



def 							UpperCamelCase__			(			):


						'''simple docstring'''






						for _ in range(1_0_0      ):
												# 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 							UpperCamelCase__			(			):


						'''simple docstring'''






						_lowerCAmelCase										=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'''

def 							UpperCamelCase__			(			a__ = 1_0_0_0      ):


						'''simple docstring'''






						_lowerCAmelCase										=2**power
						_lowerCAmelCase										=0
						while n:
												_lowerCAmelCase						,				_lowerCAmelCase										=r + n % 1_0, n // 1_0
						return r


if __name__ == "__main__":
							print(solution(int(str(input()).strip())))





