题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。

请为这种高级打字机设计一个程序，支持如下 $3$ 种操作：

1. T x：Type 操作，表示在文章末尾打下一个小写字母 $x$。
2. U x：Undo 操作，表示撤销最后的 $x$ 次修改操作。
3. Q x：Query 操作，表示询问当前文章中第 $x$ 个字母并输出。请注意 Query 操作并不算修改操作。

文章一开始可以视为空串。

输入格式

第 $1$ 行：一个整数 $n$，表示操作数量。

以下 $n$ 行，每行一个命令。保证输入的命令合法。

输出格式

每行输出一个字母，表示 Query 操作的答案。

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

b
c

提示

数据范围及约定

• 对于 $40\%$ 的数据 $n \le 200$。
• 对于 $100\%$ 的数据 $n \le 100000$，同时保证 Undo 操作不会撤销 Undo 操作。

高级挑战

对于 $200\%$ 的数据 $n \le 100000$，Undo 操作可以撤销 Undo 操作。

IOI 挑战

必须使用在线算法完成该题。