Taco's Min-Heap Operations

In this problem, you are required to implement a Min-Heap supporting several operations. The Min-Heap is stored in an array representing a complete binary tree. You need to implement the following operations with an expected time complexity of (O(\log N)) per operation:

1. insert(x): Insert the element (x) into the heap.
2. extractMin: Remove and return the smallest element in the heap. It is guaranteed that this operation is not called when the heap is empty.
3. decreaseKey(i, x): Decrease the value of the element at index (i) (0-indexed) to (x). It is guaranteed that (x) is less than or equal to the current value at index (i).
4. delete(i): Delete the element at index (i) from the heap. You may implement deletion by decreasing the key to (-\infty) and then extracting the minimum.

The heap property must be maintained after each operation. The indices for the operations (decreaseKey) and (delete) refer to the position of the element in the current heap array (0-indexed).

Your program will process a sequence of operations read from standard input and should output the result of each extractMin operation to standard output.

inputFormat

The first line contains an integer (Q), the number of operations. The next (Q) lines each contain an operation in one of the following formats:

• For insertion: 1 x where (x) is an integer to be inserted. • For extracting the minimum: 2 • For decreasing a key: 3 i x where (i) is the 0-indexed position in the heap array and (x) is the new value ((x) will be less than or equal to the current value at index (i)). • For deletion: 4 i where (i) is the 0-indexed position in the heap array to be deleted.

It is guaranteed that the operations are valid and no extractMin operation is called on an empty heap.

outputFormat

For every extractMin operation (2), output the extracted minimum element on a separate line to standard output.## sample

6
1 3
1 2
1 1
2
2
2

1
2
3