Background

Translated from POI2021~2022R2 Day2T2。

Problem Description

There is a dance party. At the beginning, there are only persons $1$ and $2$, and both of them are willing to dance with each other.

Then there are $q$ events, corresponding to the following operations:

• W x: A new person joins. They and person $x$ are mutually willing to dance with each other.
• Z x: A new person joins. Initially, they are mutually willing to dance with everyone that person $x$ is willing to dance with.
• ? x: Query how many people are willing to dance with $x$.

The new person’s index is the current number of people plus one.

Input Format

The first line contains an integer $q\ (1 \leq q \leq 10^6)$.

Then follow $q$ lines. Each line contains a character and an integer $x$, with the meaning as described above.

Output Format

For each ? operation, output one line with the answer.

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

1
2
3
2

Hint

Sample explanation:

Subtasks:

Translated by ChatGPT 5