Undoable Typewriter

In this problem, you are to implement an advanced typewriter with undo functionality. Initially, the document is empty. The typewriter supports three operations:

1. (T\ x): Append a lowercase letter (x) to the end of the document.
2. (U\ x): Undo the last (x) modification operations (only the type operations are considered modifications).
3. (Q\ x): Query the (x)th character of the current document and output it.

Note: Query operations are not considered modification operations.

inputFormat

The first line contains an integer (n), the number of operations. Each of the following (n) lines contains one operation in one of the following formats:

• T x: Append the character (x) to the document. (x) is a lowercase letter.
• U x: Undo the last (x) type operations.
• Q x: Output the (x)th character of the current document.

It is guaranteed that the operations are valid.

outputFormat

For each query operation, output the corresponding character on a new line.

sample

5
T a
T b
Q 2
U 1
Q 1

b
a