Description

Some people say that Leonardo was an admirer of Johannes Gutenberg. Johannes was a German blacksmith who invented movable-type printing. To show his respect, Leonardo designed a machine called the “crayfish scrivener”, which is a very simple typing device. This machine is like a simple modern typewriter, but it can only accept two commands. One command outputs a character, and the other command cancels the most recent command. The most important feature of the crayfish scrivener is its powerful undo command. Since an undo command is itself a command, it can also be undone.

Note

Your task is to write the program for this crayfish scrivener. At the beginning, nothing is output. Then the program receives a sequence of user commands, and it should be able to answer queries asking for the character at a specific position in the current output text. The details are as follows:

• TypeLetter(L) — append a lowercase letter $L$ to the end of the output text, where $L$ can be $a,b,\cdots, z$.

• UndoCommands(U) — undo the previous $U$ commands, where $U$ is a positive integer.

• GetLetter(P) — return the character at position $P$ in the output text, where $P$ is a non-negative integer. The first character in the output text is at position $0$. (This query is not a command, so it is ignored by undo commands.)

The three operations may be called in any order, $0$ or more times.

The command UndoCommands(U) undoes the previous $U$ commands in the reverse order of their execution: if an undone command is TypeLetter(L), then the letter $L$ is removed from the end of the output text. If an undone command is UndoCommands(X), then the previously undone $X$ commands will be executed again in their original order.

Example

We list a possible sequence of commands and the output text after each operation.

Input Format

• Line $1$: a positive integer $N$, the number of operations.

• Lines $2$ to $N+1$: each line starts with an uppercase letter indicating the operation type.

1. T indicates a TypeLetter command, followed by a space and a lowercase letter.

2. U indicates an UndoCommands command, followed by a space and an integer.

3. P indicates a GetLetter query, followed by a space and an integer.

Output Format

For each GetLetter operation, output one line containing the returned character.

10
T c
T z
T u
T a
T i
T h
T f
T z
P 3
P 0

a
c

98
T u
T g
T p
T h
T w
P 3
P 0
T d
T d
T r
T v
T z
T w
T h
P 0
T d
T v
T b
P 9
T n
T e
P 0
T s
T i
T a
P 6
T b
T n
T m
T t
T m
T g
T y
T g
P 0
T m
P 18
T r
P 17
T w
T w
T o
T m
T m
P 0
T q
P 5
T t
P 27
P 34
T p
T f
T h
T j
T f
T l
P 3
T f
T q
T h
P 17
T w
T d
T p
T z
P 0
T m
P 10
T o
P 5
P 18
P 7
T q
T z
P 2
T u
P 10
T e
P 6
T s
T t
P 24
T s
P 0
T t
T c
P 4
T j
T o
P 5
T i
P 11
T a
T t
P 58
P 51
P 64
P 12

h
u
u
z
u
d
u
i
s
u
d
g
m
h
s
u
w
d
i
r
p
w
d
m
u
w
d
h
s
o
a
d

Hint

For $100\%$ of the data, $1 \le N \le 10^6$. The parameter $U$ is guaranteed not to exceed the number of commands that have been entered so far, and the parameter $P$ is always less than the length of the output text (that is, the number of letters in the output text).

Translated by ChatGPT 5