高级打字机

题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。 请为这种高级打字机设计一个程序,支持如下 $3$ 种操作: 1. `T x`:Type 操作,表示在文章末尾打下一个小写字母 $x$。 2. `U x`:Undo 操作,表示撤销最后的 $x$ 次修改操作。 3. `Q x`:Query 操作,表示询问当前文章中第 $x$ 个字母并输出。请注意 Query 操作并不算修改操作。 文章一开始可以视为空串。

输入输出格式

输入格式


第 $1$ 行:一个整数 $n$,表示操作数量。 以下 $n$ 行,每行一个命令。保证输入的命令合法。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

b
c

说明

对于前 $20\%$ 的数据,$n\le 200$。 对于前 $50\%$ 的数据,保证 Undo 操作不会撤销 Undo 操作。 对于 $100\%$ 的数据,$n\le 10^5$。