Problem D
Friendly Interactive SHell

You might have heard about the friendly interactive shell - fish. It’s terminal based, but a bit friendlier to new users who can’t remember the commands they typed before. Fish can use your history of commands for command completion: pressing up (“^”) finds the last command you ran that shares the prefix you have already typed (a string is a prefix of itself).

If you press up again you go another step back in time, finding the second last command that shares the prefix of what you typed. If there are no more matching commands you stay at the oldest matching command.

When a series of consecutive up-presses is ended, either by typing some other character or by pressing enter to run the current command, the matching command from the history replaces everything that was typed in the current input.

When you press enter the current input is added to the command history. The command history does not contain up-characters (“^”) since command completion is always performed before the enter-key is processed.

The input to this problem contains the characters a user typed in a fish terminal, separated into lines. After each line, the user pressed enter. Your task is to output the resulting command history.

Input

The first line of the input contains a single number $n$, where $1 \leq n \leq 100\, 000$.

Then follows $n$ lines with the user input. Each line consists of characters from the alphabet $\big [$a-zA-Z0-9.^ -$\big ]$, i.e. English lower and upper case letters, digits, “-”, “ ”, “.” and the symbol “^” denoting the up key. No command begins or ends with a space.

The input is guaranteed to contain at most $10^6$ characters.

Output

For each command in the input output a line with the completed command (where all “^” are expanded). The total amount of output is guaranteed to be at most $10^6$ characters.

Sample Explanation

In Sample Input $1$ your first command is “python”. Your next command gets auto completed to “python”, and then you write “ main.py”, which is appended to your command making “python main.py”. The last command completes the first up press to “python main.py”, then “ -n 10” is typed which becomes “python main.py -n 10”.

In Sample Input $2$ your first two commands are “python” and “java”. The third command becomes auto completed to java, your previous command. The fourth command completes to “python” since it was your third last command. For your fifth command the third last command auto completed is now “java”.

In Sample Input $3$ no commands are in your history, so your up presses have no effect and only the non up presses count to your command making “python”.

3
python
p^ main.py
^ -n 10

python
python main.py
python main.py -n 10

5
python
java
^
^^^
^^^

python
java
java
python
java

1
^^^^^pyt^^hon

python