




class  __lowerCamelCase       :




    """simple docstring"""

    def __init__(       self     :     Any   ,	SCREAMING_SNAKE_CASE__     :     List[str]   )      ->       str:
         lowerCAmelCase__		= val
         # Number of nodes in left subtree
         lowerCAmelCase__		= 0
         lowerCAmelCase__		= None
         lowerCAmelCase__		= None
         lowerCAmelCase__		= None


    def    a      (       self     :     List[str]   ,	SCREAMING_SNAKE_CASE__     :     int   )      ->       Optional[int]:
         assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

         if self.val < other.val:
              lowerCAmelCase__		= self.right
              lowerCAmelCase__		= None
              if self.right:
                   lowerCAmelCase__		= other
              lowerCAmelCase__		= other
              lowerCAmelCase__		= self.left_tree_size * 2 + 1
              return self
         else:
              lowerCAmelCase__		= other.right
              lowerCAmelCase__		= None
              if other.right:
                   lowerCAmelCase__		= self
              lowerCAmelCase__		= self
              lowerCAmelCase__		= other.left_tree_size * 2 + 1
              return other






class  __lowerCamelCase       :




    """simple docstring"""

    def __init__(       self     :     Dict   ,	SCREAMING_SNAKE_CASE__     :     List[str]=None   ,	SCREAMING_SNAKE_CASE__     :     Optional[int]=None   ,	SCREAMING_SNAKE_CASE__     :     Dict=0   )      ->       List[Any]:
         lowerCAmelCase__		= heap_size
         lowerCAmelCase__		= bottom_root
         lowerCAmelCase__		= min_node


    def    a      (       self     :     List[str]   ,	SCREAMING_SNAKE_CASE__     :     Dict   )      ->       List[str]:

         # Empty heaps corner cases
         if other.size == 0:
              return None
         if self.size == 0:
              lowerCAmelCase__		= other.size
              lowerCAmelCase__		= other.bottom_root
              lowerCAmelCase__		= other.min_node
              return None
         # Update size
         lowerCAmelCase__		= self.size + other.size

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

         # Order roots by left_subtree_size
         lowerCAmelCase__		= []
         lowerCAmelCase__	,		lowerCAmelCase__		= 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)   )
                   lowerCAmelCase__		= i.parent
              else:
                   combined_roots_list.append((j, False)   )
                   lowerCAmelCase__		= j.parent
        # Insert links between them
         for i in range(len(SCREAMING_SNAKE_CASE__   ) - 1   ):
              if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
                   lowerCAmelCase__		= combined_roots_list[i + 1][0]
                   lowerCAmelCase__		= combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
         lowerCAmelCase__		= 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
                   lowerCAmelCase__		= i.left
                   lowerCAmelCase__		= i.parent.parent

                   # Merging trees
                   lowerCAmelCase__		= i.merge_trees(i.parent   )

                   # Updating links
                   lowerCAmelCase__		= previous_node
                   lowerCAmelCase__		= next_node
                   if previous_node:
                        lowerCAmelCase__		= i
                   if next_node:
                        lowerCAmelCase__		= i
              else:
                   lowerCAmelCase__		= i.parent
        # Updating self.bottom_root
         while i.left:
              lowerCAmelCase__		= i.left
         lowerCAmelCase__		= i

         # Update other
         lowerCAmelCase__		= self.size
         lowerCAmelCase__		= self.bottom_root
         lowerCAmelCase__		= self.min_node

         # Return the merged heap
         return self


    def    a      (       self     :     str   ,	SCREAMING_SNAKE_CASE__     :     Any   )      ->       Union[str, Any]:
         if self.size == 0:
              lowerCAmelCase__		= Node(SCREAMING_SNAKE_CASE__   )
              lowerCAmelCase__		= 1
              lowerCAmelCase__		= self.bottom_root
         else:
              # Create new node
              lowerCAmelCase__		= Node(SCREAMING_SNAKE_CASE__   )

              # Update size
              self.size += 1

              # update min_node
              if val < self.min_node.val:
                   lowerCAmelCase__		= new_node
              # Put new_node as a bottom_root in heap
              lowerCAmelCase__		= new_node
              lowerCAmelCase__		= self.bottom_root
              lowerCAmelCase__		= 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
                   lowerCAmelCase__		= self.bottom_root.parent.parent

                   # Merge
                   lowerCAmelCase__		= self.bottom_root.merge_trees(self.bottom_root.parent   )

                   # Update Links
                   lowerCAmelCase__		= next_node
                   lowerCAmelCase__		= None
                   if next_node:
                        lowerCAmelCase__		= self.bottom_root


    def    a      (       self     :     Optional[int]   )      ->       List[str]:
         return self.min_node.val


    def    a      (       self     :     Optional[Any]   )      ->       Optional[int]:
         return self.size == 0


    def    a      (       self     :     Dict   )      ->       Dict:
         lowerCAmelCase__		= self.min_node.val

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

              # Update bottom root
              lowerCAmelCase__		= None

              # Update min_node
              lowerCAmelCase__		= 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
              lowerCAmelCase__		= self.bottom_root.parent
              lowerCAmelCase__		= None

              # Update min_node
              lowerCAmelCase__		= self.bottom_root
              lowerCAmelCase__		= self.bottom_root.parent
              while i:
                   if i.val < self.min_node.val:
                        lowerCAmelCase__		= i
                   lowerCAmelCase__		= i.parent
              return min_value
         # General case
         # Find the BinomialHeap of the right subtree of min_node
         lowerCAmelCase__		= self.min_node.right
         lowerCAmelCase__		= None
         lowerCAmelCase__		= bottom_of_new
         lowerCAmelCase__		= 1

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

         # Update size
         lowerCAmelCase__		= self.size - 1 - size_of_new

         # Neighbour nodes
         lowerCAmelCase__		= self.min_node.left
         lowerCAmelCase__		= self.min_node.parent

         # Initialize new bottom_root and min_node
         lowerCAmelCase__		= previous_node or next_node
         lowerCAmelCase__		= next_node

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

              # Update bottom_root and search for min_node below
              lowerCAmelCase__		= previous_node
              lowerCAmelCase__		= previous_node
              while self.bottom_root.left:
                   lowerCAmelCase__		= self.bottom_root.left
                   if self.bottom_root.val < self.min_node.val:
                        lowerCAmelCase__		= self.bottom_root
         if next_node:
              lowerCAmelCase__		= previous_node

              # Search for new min_node above min_node
              lowerCAmelCase__		= next_node
              while i:
                   if i.val < self.min_node.val:
                        lowerCAmelCase__		= i
                   lowerCAmelCase__		= i.parent
        # Merge heaps
         self.merge_heaps(SCREAMING_SNAKE_CASE__   )

         return min_value


    def    a      (       self     :     Optional[Any]   )      ->       Optional[int]:
         lowerCAmelCase__		= self.bottom_root
         while top_root.parent:
              lowerCAmelCase__		= top_root.parent
         # preorder
         lowerCAmelCase__		= []
         self.__traversal(SCREAMING_SNAKE_CASE__   ,	SCREAMING_SNAKE_CASE__   )
         return heap_pre_order


    def    a      (       self     :     Union[str, Any]   ,	SCREAMING_SNAKE_CASE__     :     Dict   ,	SCREAMING_SNAKE_CASE__     :     Optional[int]   ,	SCREAMING_SNAKE_CASE__     :     Dict=0   )      ->       Any:
         if curr_node:
              preorder.append((curr_node.val, level)   )
              self.__traversal(curr_node.left   ,	SCREAMING_SNAKE_CASE__   ,	level + 1   )
              self.__traversal(curr_node.right   ,	SCREAMING_SNAKE_CASE__   ,	level + 1   )
         else:
              preorder.append(("#", level)   )


    def __str__(       self     :     List[str]   )      ->       List[Any]:
         if self.is_empty():
              return ""
         lowerCAmelCase__		= self.pre_order()

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


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

     doctest.testmod()






from __future__ import annotations

from typing import Generic, TypeVar

UpperCamelCase								=     TypeVar('T')





class  __lowerCamelCase       (    Generic[T]    ):




    """simple docstring"""

    def __init__(       self     :     List[str]   ,	SCREAMING_SNAKE_CASE__     :     T   )      ->       List[Any]:
         lowerCAmelCase__		= data  # Assign data
         lowerCAmelCase__		= None  # Initialize next as null
         lowerCAmelCase__		= None  # Initialize prev as null






class  __lowerCamelCase       (    Generic[T]    ):




    """simple docstring"""

    def __init__(       self     :     Any   )      ->       None:
         lowerCAmelCase__		= None


    def    a      (       self     :     Tuple   ,	SCREAMING_SNAKE_CASE__     :     T   )      ->       None:
         if self.head is None:
              lowerCAmelCase__		= Node(SCREAMING_SNAKE_CASE__   )
         else:
              lowerCAmelCase__		= Node(SCREAMING_SNAKE_CASE__   )
              lowerCAmelCase__		= new_node
              lowerCAmelCase__		= self.head
              lowerCAmelCase__		= None
              lowerCAmelCase__		= new_node


    def    a      (       self     :     int   )      ->       T | None:
         if self.head is None:
              return None
         else:
              assert self.head is not None
              lowerCAmelCase__		= self.head.data
              lowerCAmelCase__		= self.head.next
              if self.head is not None:
                   lowerCAmelCase__		= None
              return temp


    def    a      (       self     :     int   )      ->       T | None:
         return self.head.data if self.head is not None else None


    def __len__(       self     :     List[str]   )      ->       int:
         lowerCAmelCase__		= self.head
         lowerCAmelCase__		= 0
         while temp is not None:
              count += 1
              lowerCAmelCase__		= temp.next
         return count


    def    a      (       self     :     Tuple   )      ->       bool:
         return self.head is None


    def    a      (       self     :     Dict   )      ->       None:
         print("stack elements are:"   )
         lowerCAmelCase__		= self.head
         while temp is not None:
              print(temp.data   ,	end="->"   )
              lowerCAmelCase__		= temp.next


# Code execution starts here
if __name__ == "__main__":
     # Start with the empty stack
     UpperCamelCase								=     Stack()

     # Insert 4 at the beginning. So stack becomes 4->None
     print('Stack operations using Doubly LinkedList')
     stack.push(4)

     # Insert 5 at the beginning. So stack becomes 4->5->None
     stack.push(5)

     # Insert 6 at the beginning. So stack becomes 4->5->6->None
     stack.push(6)

     # Insert 7 at the beginning. So stack becomes 4->5->6->7->None
     stack.push(7)

     # Print the stack
     stack.print_stack()

     # Print the top element
     print('\nTop element is ', stack.top())

     # Print the stack size
     print('Size of the stack is ', len(stack))

     # pop the top element
     stack.pop()

     # pop the top element
     stack.pop()

     # two elements have now been popped off
     stack.print_stack()

     # Print True if the stack is empty else False
     print('\nstack is empty:', stack.is_empty())
