Scrivener

Implement a tiny persistent text editor that starts with an empty text and processes \(Q\) commands:

• T c — TypeLetter: append the lowercase letter \(c\).
• U u — UndoCommands: undo the last \(u\) text-modifying commands (both T and U are modifying; G is not). An U is itself a modifying command and can later be undone.
• G p — GetLetter: output the character at 0-indexed position \(p\) of the current text.

Print the answer to every G command, in order.

Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.

Interaction / I/O protocol

Input. Line 1: \(Q\). Each of the next \(Q\) lines is one command: T c, U u, or G p.

Output. For each G p, print the requested character on its own line, in the order the G commands appear.

Example. Commands Ta Tb Tc G1 U2 G0 Tx G1 output b, a, x:

after Ta Tb Tc the text is abc (G1=b); U2 returns to a (G0=a); Tx makes ax (G1=x).

• \(1 \le Q \le 100{,}000\)
• Every U u satisfies \(0 \le u \le\) (number of prior modifying commands); every G p is within the current text length.

Line 1: \(Q\). Each of the next \(Q\) lines is one command: T c, U u, or G p.

For each G p, print the requested character on its own line, in the order the G commands appear.

rip 작성

출처 IOI 2012