Crayfish scrivener

For a better understanding: http://www.ioi2012.org/wp-content/uploads/2011/12/Scrivener.pdf

Some people say that Leonardo was a great admirer of Johannes Gutenberg, the German blacksmith who invented movable-type printing, and that he paid homage by designing a machine called the crayfish scrivener — il gambero scrivano — a very simple typing device. It is somehow similar to a simple modern typewriter and accepts only two commands: one to type the next character and one to undo the most recent commands. The notable feature of the crayfish scrivener is that the undo command is extremely powerful: an undo is also considered to be a command itself,

and can be undone.

Statement

Your task is to realize a software version of the crayfish scrivener: it starts with an integer representing the number of queries and accepts a sequence of commands entered by the user, and queries for specific positions of the current version of the text, as follows.

T L — append to the end of the text a single lowercase letter L chosen from

a, …, z.

U C — undo the the last C commands, for a positive integer C.

P X — return the letter at position X in the current text, for a non-negative index X. The first letter in the text has index 0. (This query is not a command and thus is ignored by the undo command.)

It is guaranteed that C in query 'U' will not exceed the number of previously received commands, and that X in query 'P' will be less than the current text length ( the number of letter in the current text ).

As for query 'U', it undoes the previous C commands in reverse order: if the command to be undone is T L, then it removes L from the end of the current text; if the command to be undone is U X for some value X, it re-does the previous X commands in their original order.

Example

Input                                 Output

10                                       a

T c                                      c

T z

T u

T a

T i

T h

T f

T z

P 3

P 0