Dance Party

You are given a dance party scenario. Initially, there are two participants, numbered \(1\) and \(2\), and they are willing to dance with each other. Then, there are \(q\) events. The events can be of three types:

1. W x: A new participant arrives (with the next number, i.e. current total count + 1) and is willing to dance with person \(x\). This willingness is mutual, so person \(x\) is also willing to dance with the new participant.
2. Z x: A new participant arrives (numbered as current count + 1). Initially, for every person \(y\) with whom person \(x\) is willing to dance (i.e. all current dance partners of \(x\)), the new participant and \(y\) mutually become willing to dance with each other.
3. ? x: Query how many people are currently willing to dance with person \(x\).

Note: The new participant's number is always the current number of participants + 1.

All formulas are expressed in \(\LaTeX\) format. For example, the initial participants are \(1\) and \(2\), and the mutual willingness is represented by an edge between them.

inputFormat

The first line of input contains a single integer \(q\) representing the number of events.

Each of the next \(q\) lines contains an event in one of the following formats:

• W x
• Z x
• ? x

Here, \(x\) is an integer representing an existing participant's number.

outputFormat

For each query event of the form ? x, output a single line containing the number of participants that are willing to dance with person \(x\).

sample

3
? 1
W 1
? 1

1
2