Description

Sanae has bought the latest advanced typewriter. As you would expect, the latest model has a new feature: it supports undo.

Please design a program for this advanced typewriter that supports the following $3$ types of operations:

1. T x: Type operation, which appends a lowercase letter $x$ to the end of the text.
2. U x: Undo operation, which undoes the last $x$ modification operations.
3. Q x: Query operation, which asks for and outputs the $x$-th letter of the current text. Note that the Query operation does not count as a modification operation.

Initially, the text can be regarded as an empty string.

Input Format

Line $1$: an integer $n$, the number of operations.

The next $n$ lines each contain one command. It is guaranteed that the input commands are valid.

Output Format

Output one letter per line, which is the answer to each Query operation.

7
T a
T b
T c
Q 2
U 2
T c
Q 2

b
c

Hint

For the first $20\%$ of the testdata, $n \le 200$.

For the first $50\%$ of the testdata, it is guaranteed that an Undo operation will not undo an Undo operation.

For $100\%$ of the testdata, $n \le 10^5$.

Translated by ChatGPT 5