Problem E: [Medium II] Skylar's Candy Stack

Problem E: [Medium II] Skylar's Candy Stack

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 1050  Solved: 234
[Submit][Status][Web Board]

Description

Skylar is a sweet girl who has great enthusiasm for collecting various colorful candies. In her collection, the colors of different candies are numbered by integers and we regard the candies of the same color are the same. Now Skylar would like to put her candies into a candy stack and LowbieH helps her to do the work. But LowbieH is a greedy glutton. He wants to eat the candy which has the most color frequency and is the nearest one to the top of the stack. The order of the rest candies in the stack won't be disrupted. Can you help him?

Input

There are two types of input.

Type-1: put-in $$c$$. This means that LowbieH will put a candy of color $$c$$ into the candy stack, where $$c(1 \leq c \leq 10^5)$$.

Type-2: eat. This means that LowbieH will eat the candy he want.

The input is ended by a string "nsdd".

It is guaranteed that the number of the type-1 input won't exceed $$3*10^5$$ and the number of the total input won't exceed $$5*10^5$$.

Output

Print a single line with an integer $$x$$ for each type-2 input, denoting the color of the candy that LowbieH wants to eat. If the candy stack is empty, print "pa"(without quotation marks) instead.

Sample Input

put-in 5
put-in 1
put-in 4
put-in 1
eat
put-in 1
put-in 4
eat
eat
eat
eat
eat
eat
nsdd

Sample Output

1
4
1
4
1
5
pa

[Submit][Status]