Problem L
Undo
Ivan is typing in his favorite text editor, Emin. The editor keeps track of a current string, and allows performing a series of operations.
-
Ivan can type a letter, which gets added to the end of the string.
-
Ivan can press the Backspace key, which causes the the character at the end of the string (if any) to be removed.
-
Finally, Ivan can press the Undo key, which causes the most recent add or remove operation (which has not already been undone) to be undone.
Once an operation has been undone, it is as if that operation never happened, and there is no way to redo it (other than simply pressing the appropriate key again). In particular, undo operations never affect previous undo operations. If there are no previous operations left to undo, Undo has no effect.
Input
The first line of input contains an integer $n$ ($0\leq n\leq 10^5$), the number of operations.
The next $n$ lines specify one operation per line. Each operation is either Undo, Backspace, or a single upper- or lowercase letter.
Output
Output the string which is contained in the editor at the end of the editing session, followed by the character > to indicate the cursor. You may assume that the editor always starts out containing the empty string.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 h i p Undo |
hi> |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 h i p Backspace Undo |
hip> |
| Sample Input 3 | Sample Output 3 |
|---|---|
12 h m q Undo i Backspace x Undo Undo Undo Undo i |
hi> |
