Little Lobster Scribe

This problem simulates a very simple text editor, called the Little Lobster Scribe, inspired by Leonardo who admired Johannes Gutenberg. The editor supports two operations that modify the text and one query operation:

• TypeLetter(L): Appends the lowercase letter L (ie: a-z) to the end of the current text.
• UndoCommands(U): Cancels the previous U commands. Note that only TypeLetter and UndoCommands count as commands. The cancellation happens in reverse order. If the command being undone is an UndoCommands(X), then the X commands that were undone by it are reapplied (restored) in their original order.
• GetLetter(P): Outputs the character at the 0-indexed position P of the current text. This operation is a query and is not recorded as a command (and hence cannot be undone).

At the beginning, the text is empty. You will be given a series of operations. For every GetLetter operation, output the corresponding character.

The effect of the UndoCommands operation can be described formally. Let T_i be the text after the i-th command (recall that only TypeLetter and UndoCommands are commands and are numbered sequentially, starting with i = 0 for the empty text). Then:

• If the command is TypeLetter(L), then T_i = T_i-1 \; + \; L.
• If the command is UndoCommands(U), then T_i = T_i-1-U.

For example, consider the following sequence of operations and their effects:

Operation	Output	Current Text
TypeLetter(a)		a
TypeLetter(b)		ab
GetLetter(1)	b	ab
TypeLetter(d)		abd
UndoCommands(2)		a
UndoCommands(1)		abd
GetLetter(2)	d	abd
TypeLetter(e)		abde
UndoCommands(1)		abd
UndoCommands(5)		ab
TypeLetter(c)		abc
GetLetter(2)	c	abc
UndoCommands(2)		abd
GetLetter(2)	d	abd

Note that the GetLetter queries do not count as commands and hence are not affected by undo operations.

inputFormat

The first line contains an integer N — the total number of operations.

Each of the following N lines contains one operation in one of the following formats:

• TypeLetter(L) where L is a lowercase letter.
• UndoCommands(U) where U is a positive integer.
• GetLetter(P) where P is a non-negative integer indicating the position in the current text (0-indexed).

It is guaranteed that any GetLetter(P) operation has a valid position P in the current text when executed.

outputFormat

For each GetLetter operation, output the character at the specified position on a separate line.

sample

14
TypeLetter(a)
TypeLetter(b)
GetLetter(1)
TypeLetter(d)
UndoCommands(2)
UndoCommands(1)
GetLetter(2)
TypeLetter(e)
UndoCommands(1)
UndoCommands(5)
TypeLetter(c)
GetLetter(2)
UndoCommands(2)
GetLetter(2)

b
d
c
d

</p>