题目描述

早苗入手了最新的高级打字机，该打字机具备撤销功能。请为这款打字机设计程序，支持以下 3 种操作：

1. T x：在文章末尾输入一个小写字母 x（type 操作，属于修改操作）。
2. U x：撤销最后的 x 次修改操作（Undo 操作，Query 操作不算修改操作）。
3. Q x：询问当前文章中第 x 个字母并输出（Query 操作，不属于修改操作）。

文章初始为空串。

输入格式

第一行：一个整数 n，表示操作数量。 接下来 n 行，每行一个合法命令。

输出格式

对于每个 Q 操作，输出对应的字母，每行一个。

输入输出样例

输入 #1

输出 #1

样例

输入

7

输出

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

说明/提示

• 20% 的数据：n <= 200；
• 50% 的数据：n <= 100000，保证 Undo 操作不会撤销 Undo 操作；
• 100% 的数据：n <= 100000，Undo 操作可以撤销 Undo 操作；