eolymp
bolt
Try our new interface for solving problems
Problems

Maximum Frequency Stack

Maximum Frequency Stack

Time limit 1 second
Memory limit 128 MiB

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 data

Each line contains a single command.

Output data

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

Examples

Input example #1
push 4
push 5
push 4
push 6
push 7
pop
push 5
pop
pop
Output example #1
4
5
7
Input example #2
push 5
push 3
push 1
push 3
push 9
pop
pop
pop
pop
pop
Output example #2
3
9
1
3
5