




'''simple docstring'''






class  A		:




    '''simple docstring'''





    def __init__(self			,  _UpperCAmelCase      )     ->	Optional[int]:
       __UpperCamelCase				:      Tuple									=       val
       # Number of nodes in left subtree
       __UpperCamelCase				:      List[str]									=       0
       __UpperCamelCase				:      Optional[Any]									=       None
       __UpperCamelCase				:      List[str]									=       None
       __UpperCamelCase				:      Optional[Any]									=       None





    def 	a_	(self			,  _UpperCAmelCase      )     ->	Union[str, Any]:
       assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

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







class  A		:




    '''simple docstring'''





    def __init__(self			,  _UpperCAmelCase=None			,  _UpperCAmelCase=None			,  _UpperCAmelCase=0      )     ->	List[str]:
       __UpperCamelCase				:      Dict									=       heap_size
       __UpperCamelCase				:      str									=       bottom_root
       __UpperCamelCase				:      str									=       min_node
    def 	a_	(self			,  _UpperCAmelCase      )     ->	List[str]:

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

       # Update min.node
       if self.min_node.val > other.min_node.val:
          __UpperCamelCase				:      int									=       other.min_node
       # Merge

       # Order roots by left_subtree_size
       __UpperCamelCase				:      Tuple									=       []
       __UpperCamelCase				:      Dict									=       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				:      List[Any]									=       i.parent
          else:
             combined_roots_list.append((j, False)      )
             __UpperCamelCase				:      Dict									=       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				:      Dict									=       combined_roots_list[i + 1][0]
             __UpperCamelCase				:      List[Any]									=       combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
       __UpperCamelCase				:      List[Any]									=       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				:      Dict									=       i.left
             __UpperCamelCase				:      str									=       i.parent.parent

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

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

       # Update other
       __UpperCamelCase				:      Tuple									=       self.size
       __UpperCamelCase				:      Tuple									=       self.bottom_root
       __UpperCamelCase				:      str									=       self.min_node

       # Return the merged heap
       return self
    def 	a_	(self			,  _UpperCAmelCase      )     ->	str:
       if self.size == 0:
          __UpperCamelCase				:      int									=       Node(_UpperCAmelCase      )
          __UpperCamelCase				:      List[str]									=       1
          __UpperCamelCase				:      Any									=       self.bottom_root
       else:
          # Create new node
          __UpperCamelCase				:      List[str]									=       Node(_UpperCAmelCase      )

          # Update size
          self.size += 1

          # update min_node
          if val < self.min_node.val:
             __UpperCamelCase				:      Optional[Any]									=       new_node
          # Put new_node as a bottom_root in heap
          __UpperCamelCase				:      Optional[Any]									=       new_node
          __UpperCamelCase				:      Dict									=       self.bottom_root
          __UpperCamelCase				:      Dict									=       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[int]									=       self.bottom_root.parent.parent

             # Merge
             __UpperCamelCase				:      Tuple									=       self.bottom_root.merge_trees(self.bottom_root.parent      )

             # Update Links
             __UpperCamelCase				:      str									=       next_node
             __UpperCamelCase				:      str									=       None
             if next_node:
                __UpperCamelCase				:      str									=       self.bottom_root
    def 	a_	(self      )     ->	Any:
       return self.min_node.val
    def 	a_	(self      )     ->	Dict:
       return self.size == 0
    def 	a_	(self      )     ->	str:
       __UpperCamelCase				:      Optional[Any]									=       self.min_node.val

       # Last element in heap corner case
       if self.size == 1:
          # Update size
          __UpperCamelCase				:      int									=       0

          # Update bottom root
          __UpperCamelCase				:      str									=       None

          # Update min_node
          __UpperCamelCase				:      Tuple									=       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				:      str									=       self.bottom_root.parent
          __UpperCamelCase				:      Optional[int]									=       None

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

       # Size, min_node and bottom_root
       while bottom_of_new.left:
          __UpperCamelCase				:      List[Any]									=       size_of_new * 2 + 1
          __UpperCamelCase				:      Tuple									=       bottom_of_new.left
          if bottom_of_new.val < min_of_new.val:
             __UpperCamelCase				:      Optional[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				:      List[Any]									=       size_of_new
          __UpperCamelCase				:      List[str]									=       bottom_of_new
          __UpperCamelCase				:      Optional[int]									=       min_of_new
          # print("Single root, multiple nodes case")
          return min_value
       # Remaining cases
       # Construct heap of right subtree
       __UpperCamelCase				:      List[Any]									=       BinomialHeap(
           bottom_root=_UpperCAmelCase			,  min_node=_UpperCAmelCase			,  heap_size=_UpperCAmelCase      )

       # Update size
       __UpperCamelCase				:      Dict									=       self.size - 1 - size_of_new

       # Neighbour nodes
       __UpperCamelCase				:      Dict									=       self.min_node.left
       __UpperCamelCase				:      Optional[Any]									=       self.min_node.parent

       # Initialize new bottom_root and min_node
       __UpperCamelCase				:      int									=       previous_node or next_node
       __UpperCamelCase				:      Union[str, Any]									=       next_node

       # Update links of previous_node and search below for new min_node and
       # bottom_root
       if previous_node:
          __UpperCamelCase				:      Dict									=       next_node

          # Update bottom_root and search for min_node below
          __UpperCamelCase				:      Optional[int]									=       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				:      int									=       self.bottom_root
       if next_node:
          __UpperCamelCase				:      str									=       previous_node

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

       return min_value
    def 	a_	(self      )     ->	List[str]:
       __UpperCamelCase				:      Dict									=       self.bottom_root
       while top_root.parent:
          __UpperCamelCase				:      int									=       top_root.parent
       # preorder
       __UpperCamelCase				:      Union[str, Any]									=       []
       self.__traversal(_UpperCAmelCase			,  _UpperCAmelCase      )
       return heap_pre_order
    def 	a_	(self			,  _UpperCAmelCase			,  _UpperCAmelCase			,  _UpperCAmelCase=0      )     ->	Optional[int]:
       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      )     ->	Dict:
       if self.is_empty():
          return ""
       __UpperCamelCase				:      int									=       self.pre_order()

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


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

    doctest.testmod()









'''simple docstring'''






def       __lowerCAmelCase (   snake_case__ = 4_000_000						):
			__UpperCamelCase				:      Tuple									=       1
			__UpperCamelCase				:      int									=       2
			__UpperCamelCase				:      str									=       0
			while j <= n:
						if j % 2 == 0:
									total += j
						__UpperCamelCase		, __UpperCamelCase				:      List[Any]									=       j, i + j

			return total


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



