题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Konkurs tańca towarzyskiego

Bajtazar 被选为字节王国伴舞大赛的组织者。为了让报名更顺畅，他为参赛舞者设计了一份报名表。舞者们需要单独报名，每位新报名的舞者可以看到已注册的舞者名单，然后声明自己愿意与其中哪些人共舞。我们假设，如果舞者 $A$ 表示愿意与舞者 $B$ 共舞，那么舞者 $B$ 也愿意与 $A$ 共舞。

Bajtazar 发现，报名的舞者可以分为两类：挑剔型和嫉妒型。挑剔型的舞者只会从已注册的舞者中选择一人共舞；嫉妒型的舞者则声明，他们愿意与某个已注册舞者所选的相同舞伴共舞。为了简化问题，报名的舞者按自然数顺序编号，从 $1$ 开始。初始时，已有编号为 $1$ 和 $2$ 的两位舞者，他们愿意互相共舞。

Bajtazar 已经编写了一个程序来配对舞伴。为了确保程序正常运行，他需要不时查询某个指定舞者当前能与多少人共舞。请你编写一个程序，帮助他回答这些查询。

输入格式

输入的第一行包含一个整数 $q$ $(1 \leq q \leq 1000000)$，表示需要处理的操作数量。接下来的 $q$ 行，每行属于以下三种形式之一：

• $\texttt{W}\ x$：一名新的挑剔型舞者（按顺序分配下一个编号）加入，表示愿意与编号为 $x$ 的舞者共舞；
• $\texttt{Z}\ x$：一名新的嫉妒型舞者（按顺序分配下一个编号）加入，表示愿意与编号为 $x$ 的舞者所选的相同舞伴共舞；
• $\texttt{?}\ x$：Bajtazar 的程序询问，编号为 $x$ 的舞者当前能与多少人共舞（假设至少会有一次这样的询问）。

输出格式

输出应包含与输入中 $\texttt{?}$ 查询数量相同的行数，每行包含一个整数，作为对 Bajtazar 程序询问的回答。

样例 1

输入

7
? 1
Z 2
? 1
Z 1
W 2
? 2
? 3

输出

1
2
3
2

以下表格展示了每次操作后各舞者的舞伴情况，以及查询涉及的舞者：

样例 2

见附加文件下 kon1.in 和 kon1.out。

该样例先有 $8$ 名挑剔型舞者，每人选择前一位共舞；然后 $10$ 名嫉妒型舞者，每人嫉妒前 $10$ 位；最后查询所有舞者；

样例 3

见附加文件下 kon2.in 和 kon2.out。

该样例有 $2000$ 名舞者，挑剔型（与第 $1$ 位共舞）和嫉妒型（嫉妒第 $1$ 位）交替出现；半数舞者加入后及最后查询所有舞者；

样例 4

见附加文件下 kon3.in 和 kon3.out。

该样例有 $500000$ 名舞者，每人嫉妒前第 $2$ 位；每加入一人后查询该舞者。

数据范围与提示

详细子任务附加限制及分值如下表所示。