题目描述

译自 COCI 2014.11.29 T5 STOGOVI

Mirko 正在玩栈。游戏开始时，他有一个编号为 $0$ 的空栈。在游戏中的第 $i$ 步，他会选择一个存在的编号为 $v$ 的栈，将它复制一份并进行以下其中一种操作：

• 将数字 $i$ 加入新栈的顶部。
• 将新栈顶部的数字删除。
• 选择另外一个编号为 $w$ 的栈，并统计有多少个不同的数字在新栈与栈 $w$ 中同时存在。

新创建的栈编号为 $i$。

Mirko 不喜欢自己用栈模拟这个过程，所以他想要你替他写一个程序来执行这个过程。对于每个删除操作输出删除的数，且对于每个统计操作，输出统计的结果。

---

输入格式

第一行，一个整数 $N$ ($1 \le N \le 300\,000$)，表示这局游戏的步数。

游戏的步骤以时间顺序按前 $N$ 个整数编号。

以下 $N$ 行，第 $i$ 行表示游戏的第 $i$ 步，为以下三种格式之一：

• a v，表示加入操作。
• b v，表示删除操作。
• c v w，表示统计操作。

操作所涉及的编号一定在 $[0,i-1]$ 中。

保证删除操作不会操作空栈。

---

输出格式

对于每个删除或统计操作，输出一行，表示请求的数字。按照输入文件给出的操作顺序排列。

---

样例 1

输入

5
a 0
a 1
b 2
c 2 3
b 4

输出

2
1
2

解释
开始时，我们有栈 $S_0 = \{\}$。
第一步，我们复制 $S_0$ 并将数字 $1$ 加入到顶部，$S_1 = \{1\}$。
第二步，我们复制 $S_1$ 并将数字 $2$ 加入到顶部，$S_2 = \{1,2\}$。
第三步，我们复制 $S_2$ 并删除数字 $2$，$S_3 = \{1\}$。
第四步，我们复制 $S_2$ 并编号为 $S_4$，统计 $S_4$ 与 $S_3$ 间不同的数字个数。唯一不同的数字是 $1$，所以答案为 $1$。
第五步，我们复制 $S_4$ 并删除数字 $2$，$S_5 = \{1\}$。

---

样例 2

输入

11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

输出

2
2
8
8

---

数据范围与提示

• $1 \le N \le 300\,000$
• 所有操作涉及的栈编号保证在合法范围内
• 删除操作不会对空栈执行