409769: GYM103736 J IHI's Magic String

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.

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$$$.

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

Otherwise, output the final string in one line.

5
1 a
1 b
1 c
3 a c
1 b

cbcb

6
1 a
1 b
1 c
1 c
3 a c
3 c a

abaa

5
1 a
1 c
3 a c
2
2

The final string is empty