Word Prediction System

You are given a series of commands that either add a sentence to a word prediction system or request a prediction based on a given prefix. When a sentence is added using the command add_sentence S, the system extracts every prefix (starting from the first word up to the penultimate word) and records the frequency of the word that immediately follows that prefix. For a query command get_prediction Q, the system returns the word w that maximizes the frequency function

[ f(Q, w) = \text{number of times } w \text{ follows } Q ]

If multiple words have the same maximum frequency, the lexicographically smallest one is chosen. If no prediction exists, output an empty string.

Input is provided from standard input and output should be written to standard output.

inputFormat

The first line contains an integer N representing the number of commands. Each of the next N lines contains a command. A command is either:

• add_sentence S where S is a sentence consisting of words separated by spaces.
• get_prediction Q where Q is a query consisting of words separated by spaces.

All input is read from standard input.

outputFormat

For each get_prediction command, output the predicted word on a new line. If there is no prediction, output an empty line. All output should be written to standard output.

## sample

7
add_sentence i love programming
add_sentence i love coding
add_sentence i love programming because it is fun
get_prediction i love
get_prediction i
add_sentence i love solving problems
get_prediction i love

programming
love
programming

</p>