Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack. The possible commands are:

• push n — pushes an integer $n$ onto the top of the stack;

• pop — removes and prints the most frequent element in the stack. If there is a tie for the most frequent element, the element closest to the stack's top is removed and printed.

Input

Each line contains a single command.

Output

For each pop command print on a separate line the corresponding result.

Examples