P6166 [IOI 2012] scrivener

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. | Operation | Return | Output text | | :-----------: | :-----------: | :-----------: | | `TypeLetter(a)` | | `a` | | `TypeLetter(b)` | | `ab` | | `GetLetter(1)` | `b` | `ab` | | `TypeLetter(d)` | | `abd` | | `UndoCommands(2)` | | `a` | | `UndoCommands(1)` | | `abd` | | `GetLetter(2)` | `d` | `abd` | | `TypeLetter(e)`| | `abde` | | `UndoCommands(1)` | | `abd` | | `UndoCommands(5)` | | `ab` | |`TypeLetter(c)` | | `abc` | | `GetLetter(2)` | `c` | `abc` | | `UndoCommands(2)` | | `abd` | | `GetLetter(2)` | `d` | `abd` |

- 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.

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

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