J. IHI's Magic String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

IHI has recently acquired a magic power that can perform the following operations on strings:

  1. puts a character at the end of a string.
  2. deletes a character at the end of a string (does not operate if the string is empty).
  3. replaces all current character $$$x$$$ in the string to characters $$$y$$$.

All characters are lowercase.

Now IHI has a string that starts empty, he wants to know what the final string is after $$$q$$$ operations.

Input

The first line contains a number $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ indicating the number of operations.

The next $$$q$$$ lines represent $$$q$$$ operations.

There are three types of operations:

  • $$$1$$$ $$$x$$$: In the first operation, you should put character $$$x$$$ at the end of the string.
  • $$$2$$$: In the second operation, you should delete a character at the end of the string if and only if this string is not empty.
  • $$$3$$$ $$$x$$$ $$$y$$$: In the third operation, replace $$$x$$$ in the string with $$$y$$$.
Output

If the final string is empty, you should output "The final string is empty".

Otherwise, output the final string in one line.

Examples
Input
5
1 a
1 b
1 c
3 a c
1 b
Output
cbcb
Input
6
1 a
1 b
1 c
1 c
3 a c
3 c a
Output
abaa
Input
5
1 a
1 c
3 a c
2
2
Output
The final string is empty