P1383 Advanced Typewriter

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.

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 one letter per line, which is the answer to each Query operation.

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