The Crayfish Scrivener

Johannes Gutenberg, the German blacksmith who invented the printing press, was someone Leonardo deeply admired. To honor Gutenberg, Leonardo designed a very simple typing machine called the crayfish scrivener — il gambero scrivano. It works much like a modern typewriter but accepts only two kinds of commands: one types the next character, and the other undoes the most recent commands. The remarkable feature of this machine is its undo, which is extremely powerful: an undo command can be applied to undo commands themselves.

Your task is to implement software that behaves like the crayfish scrivener: start from empty text, process the sequence of commands the user enters, and answer queries about the character at a given position in the current text.

• Init() — called exactly once at the very beginning with no arguments; it may initialize your data structures and is never undone.
• TypeLetter(L) — append a single lowercase letter L (one of a, …, z) to the end of the text.
• UndoCommands(U) — for a positive integer U, undo the most recent U commands.
• GetLetter(P) — for a non-negative index P, return the character at position P of the current text. The first character has index 0. (This query is not a command, so it is ignored by undo.)

After Init(), the other routines may be called in any order zero or more times. U never exceeds the number of commands issued so far, and P is always less than the length of the current text.

UndoCommands(U) undoes the previous U commands in reverse order. If the command being undone is TypeLetter(L), it deletes that L from the end of the current text. If the command being undone is UndoCommands(X) for some value X, it re-executes the previous X commands in their original order.

The following shows one possible sequence of calls and the state of the text after each call.

The first line contains L, the total number of commands and queries. Each of the next L lines contains one command or query.

• T L — call TypeLetter(L) (L is a single lowercase letter).
• U U — call UndoCommands(U) (U is a positive integer).
• P P — call GetLetter(P) (P is a non-negative integer).

The first character on each line indicates the kind, and arguments are separated by a single space.

Print the character returned by each GetLetter query, one per line, in the order the queries were made.