
'''simple docstring'''


class 		__lowercase			:

			def __init__(self ):
								lowerCamelCase_   : List[Any]       =						{}
								# indexmap keys are an index and it's values are the number at that index
								lowerCamelCase_   : List[str]       =						{}

			def     UpperCAmelCase__	(self     ,				A     ,				A ):






								if isinstance(SCREAMING_SNAKE_CASE_     ,				(range, str) ):
													lowerCamelCase_   : Union[str, Any]       =						list(SCREAMING_SNAKE_CASE_ )
								elif not isinstance(SCREAMING_SNAKE_CASE_     ,				SCREAMING_SNAKE_CASE_ ):
													raise TypeError(
													    '''binary_search_delete() only accepts either a list, range or str''' )

								lowerCamelCase_   : int       =						0
								lowerCamelCase_   : Dict       =						len(SCREAMING_SNAKE_CASE_ ) - 1

								while low <= high:
													lowerCamelCase_   : int       =						(low + high) // 2
													if array[mid] == item:
																		array.pop(SCREAMING_SNAKE_CASE_ )
																		return array
													elif array[mid] < item:
																		lowerCamelCase_   : Any       =						mid + 1
													else:
																		lowerCamelCase_   : Optional[int]       =						mid - 1
								raise ValueError(
								    '''Either the item is not in the array or the array was unsorted''' )

			def     UpperCAmelCase__	(self     ,				A     ,				A ):






								if isinstance(SCREAMING_SNAKE_CASE_     ,				(range, str) ):
													lowerCamelCase_   : Dict       =						list(SCREAMING_SNAKE_CASE_ )
								elif not isinstance(SCREAMING_SNAKE_CASE_     ,				SCREAMING_SNAKE_CASE_ ):
													raise TypeError(
													    '''binary_search_insert() only accepts either a list, range or str''' )

								lowerCamelCase_   : List[Any]       =						0
								lowerCamelCase_   : Any       =						len(SCREAMING_SNAKE_CASE_ ) - 1

								while low <= high:
													lowerCamelCase_   : Tuple       =						(low + high) // 2
													if array[mid] == index:
																		# If the item already exists in the array,
																		# insert it after the existing item
																		array.insert(mid + 1     ,				SCREAMING_SNAKE_CASE_ )
																		return array
													elif array[mid] < index:
																		lowerCamelCase_   : Optional[int]       =						mid + 1
													else:
																		lowerCamelCase_   : List[Any]       =						mid - 1

        # If the item doesn't exist in the array, insert it at the appropriate position
								array.insert(SCREAMING_SNAKE_CASE_     ,				SCREAMING_SNAKE_CASE_ )
								return array

			def     UpperCAmelCase__	(self     ,				A     ,				A ):






								if index in self.indexmap:
													lowerCamelCase_   : Optional[int]       =						self.indexmap[index]
													if len(self.numbermap[n] ) == 1:
																		del self.numbermap[n]
													else:
																		lowerCamelCase_   : Union[str, Any]       =						self.binary_search_delete(self.numbermap[n]     ,				SCREAMING_SNAKE_CASE_ )

        # Set new index
								lowerCamelCase_   : Any       =						number

								# Number not seen before or empty so insert number value
								if number not in self.numbermap:
													lowerCamelCase_   : Optional[Any]       =						[index]

								# Here we need to perform a binary search insertion in order to insert
								# The item in the correct place
								else:
													lowerCamelCase_   : str       =						self.binary_search_insert(
													    self.numbermap[number]     ,				SCREAMING_SNAKE_CASE_ )






			def     UpperCAmelCase__	(self     ,				A ):
								return self.numbermap.get(SCREAMING_SNAKE_CASE_     ,				[-1] )[0]


if __name__ == "__main__":
					import doctest

					doctest.testmod()




'''simple docstring'''


def lowercase_		(				_lowercase			)       ->							int:
					'''simple docstring'''

					if not isinstance(_lowercase     ,    _lowercase			):
										raise TypeError('''recursive_lucas_number accepts only integer arguments.'''			)
					if n_th_number == 0:
										return 2
					if n_th_number == 1:
										return 1

					return recursive_lucas_number(n_th_number - 1			) + recursive_lucas_number(
					    n_th_number - 2			)




def lowercase_		(				_lowercase			)       ->							int:
					'''simple docstring'''

					if not isinstance(_lowercase     ,    _lowercase			):
										raise TypeError('''dynamic_lucas_number accepts only integer arguments.'''			)
					lowerCamelCase_, lowerCamelCase_   : List[Any]       =						2, 1
					for _ in range(_lowercase			):
										lowerCamelCase_, lowerCamelCase_   : Dict       =						b, a + b
					return a


if __name__ == "__main__":
					from doctest import testmod

					testmod()
					__lowercase							:				Any					=       int(input('''Enter the number of terms in lucas series:\n''').strip())
					print('''Using recursive function to calculate lucas series:''')
					print(''' '''.join(str(recursive_lucas_number(i)) for i in range(n)))
					print('''\nUsing dynamic function to calculate lucas series:''')
					print(''' '''.join(str(dynamic_lucas_number(i)) for i in range(n)))


