Min Stack

You are required to design a data structure Min Stack which supports the following operations in constant time:

• push(x): Push an integer x onto the stack.
• pop(): Remove the element on top of the stack.
• top(): Get the top element of the stack. If the stack is empty, return null.
• getMin(): Retrieve the minimum element in the stack. If the stack is empty, return null.

The operations must run in O(1) time. One common method is to use an auxiliary stack to track the minimum element. In mathematical terms, if we denote by S the main stack and by M the stack of current minimums, then when pushing an element x, we perform:

\( M.push(x) \) if \( M.empty() \) or \( x \leq M.top() \).

This ensures that \( M.top() \) always represents the minimum of \( S \).

inputFormat

The first line contains an integer n representing the number of operations.

The following n lines each contain one of the following commands:

• push x: Push the integer x onto the stack.
• pop: Remove the top element from the stack.
• top: Print the top element of the stack. If the stack is empty, print null.
• getMin: Print the minimum element in the stack. If the stack is empty, print null.

outputFormat

For each top and getMin command, output the corresponding result on a new line (in the order they appear in the input). If the stack is empty when these commands are issued, output null.

## sample

7
push -2
push 0
push -3
getMin
pop
top
getMin

-3
0
-2

</p>