Bajtazar 被选为 Bajtocki 社交舞大赛的组织者。为了简化报名流程，Bajtazar 为报名的舞者准备了一份表格。参赛者逐一注册。每位报名者在注册时都能看到已经注册的舞者，并声明他们可以与其中的哪些人跳舞。我们假设如果 A 声明愿意与 B 跳舞，那么 B 也可以与 A 跳舞。

Bajtazar 注意到，报名的舞者可以分为“挑剔型”和“嫉妒型”。挑剔型舞者声明在已注册的人中，他们只能与一个人跳舞。嫉妒型舞者声明在已注册的人中，他们可以与编号为 $x$ 的舞者所能跳舞的所有人跳舞。为了简化起见，报名参赛者按自然数顺序编号，从 1 开始。最初，编号为 1 和 2 的参赛者已经注册，且他们可以互相跳舞。

Bajtazar 已经编写了一个程序来将参赛者配对。为了使他的程序正常工作，Bajtazar 需要不时地查询他指定的某位参赛者当前可以与多少人跳舞。你的任务是编写一个程序，帮助 Bajtazar 回答这些查询。

输入格式

输入的第一行包含一个整数 $q$ ($1 \le q \le 1\,000\,000$)，表示要处理的操作数量。接下来的 $q$ 行中，每一行都是以下形式之一：

• W x – 表示来了一位新的挑剔型舞者（编号递增），他声明可以与编号为 $x$ 的人跳舞；
• Z x – 表示来了一位新的嫉妒型舞者（编号递增），他声明在已注册的人中，他可以与编号为 $x$ 的人所能跳舞的所有人跳舞；
• ? x – 表示询问 Bajtazar 的程序，编号为 $x$ 的人在当前时刻可以与多少人跳舞（你可以假设 Bajtazar 的程序总是会至少进行一次此类查询）。

输出格式

输出应包含与输入中 ? 查询次数完全相同的行数。后续行应包含一个整数，即对 Bajtazar 程序查询的回答。

样例

输入格式 1

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

输出格式 1

1
2
3
2

说明

样例说明：下表描述了在后续注册后，人们可以与谁跳舞，以及查询涉及哪些参与者：

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。