G :: Final Problem

Time Limit: 5 Seconds    Memory Limit: 25600 KB

As you know, we, human beings, invented words to be able to convey our messages to each other in a clear and unambiguous way. But since everything is being changed based on our priorities, we cannot trust to meaning of words anymore. Here we just want to focus on one of them.

In priority-land, these days there is a new definition for word “final”. Based on the new definition, something is final, when it's closest thing to the last thing but not the last one itself!

For example, if we had a list of dates, as six-digit numbers, [940821,940905, 940828,940912,940716], traditionally 940912 would be the final date but priority-wise and based on new definition, 940905 is considered as final date.

Given a stream of dates, your task is to print the final date once in a while.

Input

There are a bunch of queries that end with the word “END”.

Each query could be a date in a six-digit format, which means you need to add this new date to the previous dates, or word “GetFinal”, which means you need to print the final date so far. It's guaranteed that “GetFinal” shows up when there is more than one date.

Output

For each “GetFinal” query, write the final date so far in a line.

Sample Input

940821 
940905 
GetFinal
940828 
940912 
940716
GetFinal
END

Sample Output

940821
940905

Submit

Source: 13th Iran Nationwide Internet Contest - SBU