





'''simple docstring'''






def      lowercase  (  lowerCAmelCase :						Any):



				"""simple docstring"""


				if not isinstance(_UpperCAmelCase   , _UpperCAmelCase):
								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  (  lowerCAmelCase :						Union[str, Any]):



				"""simple docstring"""


				if not isinstance(_UpperCAmelCase   , _UpperCAmelCase):
								raise TypeError('''dynamic_lucas_number accepts only integer arguments.''')
				_A :				Union[str, Any]				=  2, 1
				for _ in range(_UpperCAmelCase):
								_A :				Optional[int]				=  b, a + b
				return a


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

	testmod()
	__UpperCamelCase      :   Optional[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)))







'''simple docstring'''

class      SCREAMING_SNAKE_CASE__      :







					"""simple docstring"""






					def __init__(   self       :      Tuple		,	UpperCAmelCase_       :      Dict		):







							"""simple docstring"""
							__UpperCAmelCase	:							Any     =     val
							# Number of nodes in left subtree
							__UpperCAmelCase	:							Dict     =     0
							__UpperCAmelCase	:							int     =     None
							__UpperCAmelCase	:							Optional[int]     =     None
							__UpperCAmelCase	:							List[str]     =     None






					def 		lowerCamelCase_   (   self       :      int		,	UpperCAmelCase_       :      Optional[Any]		):







							"""simple docstring"""
							assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

							if self.val < other.val:
									__UpperCAmelCase	:							str     =     self.right
									__UpperCAmelCase	:							Tuple     =     None
									if self.right:
											__UpperCAmelCase	:							int     =     other
									__UpperCAmelCase	:							List[str]     =     other
									__UpperCAmelCase	:							Any     =     self.left_tree_size * 2 + 1
									return self
							else:
									__UpperCAmelCase	:							List[Any]     =     other.right
									__UpperCAmelCase	:							Union[str, Any]     =     None
									if other.right:
											__UpperCAmelCase	:							List[str]     =     self
									__UpperCAmelCase	:							Optional[Any]     =     self
									__UpperCAmelCase	:							Any     =     other.left_tree_size * 2 + 1
									return other






class      SCREAMING_SNAKE_CASE__      :







					"""simple docstring"""






					def __init__(   self       :      Optional[int]		,	UpperCAmelCase_       :      Optional[int]=None		,	UpperCAmelCase_       :      Optional[int]=None		,	UpperCAmelCase_       :      Optional[int]=0		):







							"""simple docstring"""
							__UpperCAmelCase	:							Any     =     heap_size
							__UpperCAmelCase	:							Any     =     bottom_root
							__UpperCAmelCase	:							List[str]     =     min_node
					def 		lowerCamelCase_   (   self       :      List[str]		,	UpperCAmelCase_       :      Dict		):







							"""simple docstring"""

							# Empty heaps corner cases
							if other.size == 0:
									return None
							if self.size == 0:
									__UpperCAmelCase	:							Dict     =     other.size
									__UpperCAmelCase	:							Optional[Any]     =     other.bottom_root
									__UpperCAmelCase	:							str     =     other.min_node
									return None
							# Update size
							__UpperCAmelCase	:							str     =     self.size + other.size

							# Update min.node
							if self.min_node.val > other.min_node.val:
									__UpperCAmelCase	:							Tuple     =     other.min_node
							# Merge

							# Order roots by left_subtree_size
							__UpperCAmelCase	:							int     =     []
							__UpperCAmelCase  ,			__UpperCAmelCase	:							List[str]     =     self.bottom_root, other.bottom_root
							while i or j:
									if i and ((not j) or i.left_tree_size < j.left_tree_size):
											combined_roots_list.append((i, True)		)
											__UpperCAmelCase	:							Optional[Any]     =     i.parent
									else:
											combined_roots_list.append((j, False)		)
											__UpperCAmelCase	:							Tuple     =     j.parent
        # Insert links between them
							for i in range(len(UpperCAmelCase_		) - 1		):
									if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
											__UpperCAmelCase	:							Optional[Any]     =     combined_roots_list[i + 1][0]
											__UpperCAmelCase	:							Any     =     combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
							__UpperCAmelCase	:							List[str]     =     combined_roots_list[0][0]
							while i.parent:
									if (
									    (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
									) or (
									    i.left_tree_size == i.parent.left_tree_size
									    and i.left_tree_size != i.parent.parent.left_tree_size
									):
											# Neighbouring Nodes
											__UpperCAmelCase	:							List[str]     =     i.left
											__UpperCAmelCase	:							Dict     =     i.parent.parent

											# Merging trees
											__UpperCAmelCase	:							Optional[int]     =     i.merge_trees(i.parent		)

											# Updating links
											__UpperCAmelCase	:							Dict     =     previous_node
											__UpperCAmelCase	:							Union[str, Any]     =     next_node
											if previous_node:
													__UpperCAmelCase	:							List[str]     =     i
											if next_node:
													__UpperCAmelCase	:							Dict     =     i
									else:
											__UpperCAmelCase	:							Optional[int]     =     i.parent
        # Updating self.bottom_root
							while i.left:
									__UpperCAmelCase	:							str     =     i.left
							__UpperCAmelCase	:							List[Any]     =     i

							# Update other
							__UpperCAmelCase	:							int     =     self.size
							__UpperCAmelCase	:							Dict     =     self.bottom_root
							__UpperCAmelCase	:							Union[str, Any]     =     self.min_node

							# Return the merged heap
							return self
					def 		lowerCamelCase_   (   self       :      Tuple		,	UpperCAmelCase_       :      Optional[int]		):







							"""simple docstring"""
							if self.size == 0:
									__UpperCAmelCase	:							Optional[Any]     =     Node(UpperCAmelCase_		)
									__UpperCAmelCase	:							Optional[Any]     =     1
									__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root
							else:
									# Create new node
									__UpperCAmelCase	:							Optional[Any]     =     Node(UpperCAmelCase_		)

									# Update size
									self.size += 1

									# update min_node
									if val < self.min_node.val:
											__UpperCAmelCase	:							Optional[int]     =     new_node
									# Put new_node as a bottom_root in heap
									__UpperCAmelCase	:							Union[str, Any]     =     new_node
									__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root
									__UpperCAmelCase	:							List[str]     =     new_node

									# Consecutively merge roots with same left_tree_size
									while (
									    self.bottom_root.parent
									    and self.bottom_root.left_tree_size
									    == self.bottom_root.parent.left_tree_size
									):
											# Next node
											__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root.parent.parent

											# Merge
											__UpperCAmelCase	:							str     =     self.bottom_root.merge_trees(self.bottom_root.parent		)

											# Update Links
											__UpperCAmelCase	:							int     =     next_node
											__UpperCAmelCase	:							Any     =     None
											if next_node:
													__UpperCAmelCase	:							Any     =     self.bottom_root
					def 		lowerCamelCase_   (   self       :      Any		):







							"""simple docstring"""
							return self.min_node.val
					def 		lowerCamelCase_   (   self       :      str		):







							"""simple docstring"""
							return self.size == 0
					def 		lowerCamelCase_   (   self       :      int		):







							"""simple docstring"""
							__UpperCAmelCase	:							str     =     self.min_node.val

							# Last element in heap corner case
							if self.size == 1:
									# Update size
									__UpperCAmelCase	:							Optional[int]     =     0

									# Update bottom root
									__UpperCAmelCase	:							List[str]     =     None

									# Update min_node
									__UpperCAmelCase	:							int     =     None

									return min_value
							# No right subtree corner case
							# The structure of the tree implies that this should be the bottom root
							# and there is at least one other root
							if self.min_node.right is None:
									# Update size
									self.size -= 1

									# Update bottom root
									__UpperCAmelCase	:							Union[str, Any]     =     self.bottom_root.parent
									__UpperCAmelCase	:							str     =     None

									# Update min_node
									__UpperCAmelCase	:							int     =     self.bottom_root
									__UpperCAmelCase	:							int     =     self.bottom_root.parent
									while i:
											if i.val < self.min_node.val:
													__UpperCAmelCase	:							Union[str, Any]     =     i
											__UpperCAmelCase	:							Optional[int]     =     i.parent
									return min_value
							# General case
							# Find the BinomialHeap of the right subtree of min_node
							__UpperCAmelCase	:							Optional[int]     =     self.min_node.right
							__UpperCAmelCase	:							List[Any]     =     None
							__UpperCAmelCase	:							Optional[int]     =     bottom_of_new
							__UpperCAmelCase	:							Union[str, Any]     =     1

							# Size, min_node and bottom_root
							while bottom_of_new.left:
									__UpperCAmelCase	:							str     =     size_of_new * 2 + 1
									__UpperCAmelCase	:							List[str]     =     bottom_of_new.left
									if bottom_of_new.val < min_of_new.val:
											__UpperCAmelCase	:							Union[str, Any]     =     bottom_of_new
        # Corner case of single root on top left path
							if (not self.min_node.left) and (not self.min_node.parent):
									__UpperCAmelCase	:							Optional[Any]     =     size_of_new
									__UpperCAmelCase	:							List[str]     =     bottom_of_new
									__UpperCAmelCase	:							List[Any]     =     min_of_new
									# print("Single root, multiple nodes case")
									return min_value
							# Remaining cases
							# Construct heap of right subtree
							__UpperCAmelCase	:							Union[str, Any]     =     BinomialHeap(
							    bottom_root=UpperCAmelCase_		,	min_node=UpperCAmelCase_		,	heap_size=UpperCAmelCase_		)

							# Update size
							__UpperCAmelCase	:							Any     =     self.size - 1 - size_of_new

							# Neighbour nodes
							__UpperCAmelCase	:							Union[str, Any]     =     self.min_node.left
							__UpperCAmelCase	:							List[str]     =     self.min_node.parent

							# Initialize new bottom_root and min_node
							__UpperCAmelCase	:							Optional[Any]     =     previous_node or next_node
							__UpperCAmelCase	:							Optional[Any]     =     next_node

							# Update links of previous_node and search below for new min_node and
							# bottom_root
							if previous_node:
									__UpperCAmelCase	:							List[str]     =     next_node

									# Update bottom_root and search for min_node below
									__UpperCAmelCase	:							List[str]     =     previous_node
									__UpperCAmelCase	:							int     =     previous_node
									while self.bottom_root.left:
											__UpperCAmelCase	:							Dict     =     self.bottom_root.left
											if self.bottom_root.val < self.min_node.val:
													__UpperCAmelCase	:							Union[str, Any]     =     self.bottom_root
							if next_node:
									__UpperCAmelCase	:							Tuple     =     previous_node

									# Search for new min_node above min_node
									__UpperCAmelCase	:							Optional[int]     =     next_node
									while i:
											if i.val < self.min_node.val:
													__UpperCAmelCase	:							List[Any]     =     i
											__UpperCAmelCase	:							List[Any]     =     i.parent
        # Merge heaps
							self.merge_heaps(UpperCAmelCase_		)

							return min_value
					def 		lowerCamelCase_   (   self       :      Union[str, Any]		):







							"""simple docstring"""
							__UpperCAmelCase	:							Tuple     =     self.bottom_root
							while top_root.parent:
									__UpperCAmelCase	:							Optional[int]     =     top_root.parent
							# preorder
							__UpperCAmelCase	:							Union[str, Any]     =     []
							self.__traversal(UpperCAmelCase_		,	UpperCAmelCase_		)
							return heap_pre_order
					def 		lowerCamelCase_   (   self       :      Optional[int]		,	UpperCAmelCase_       :      Optional[Any]		,	UpperCAmelCase_       :      int		,	UpperCAmelCase_       :      Dict=0		):







							"""simple docstring"""
							if curr_node:
									preorder.append((curr_node.val, level)		)
									self.__traversal(curr_node.left		,	UpperCAmelCase_		,	level + 1		)
									self.__traversal(curr_node.right		,	UpperCAmelCase_		,	level + 1		)
							else:
									preorder.append(("#", level)		)






					def __str__(   self       :      Optional[int]		):







							"""simple docstring"""
							if self.is_empty():
									return ""
							__UpperCAmelCase	:							Optional[Any]     =     self.pre_order()

							return "\n".join(("-" * level + str(UpperCAmelCase_		)) for value, level in preorder_heap		)


# Unit Tests
if __name__ == "__main__":
			import doctest

			doctest.testmod()




