Bajtazar has been chosen as the organizer of the Bajtocki Ballroom Dance Competition. To streamline registration for the competition, Bajtazar has prepared a form for dancers signing up. Participants register for the competition one by one. Each person signing up sees the dancers already registered and then declares which of these people they could dance with. We assume that if person A declares a desire to dance with person B, then person B can dance with person A.

Bajtazar noticed that the dancers signing up can be divided into "picky" and "jealous" types. Picky people declare that among the already registered people, they can dance with only one person. Jealous people declare that among the already registered people, they can dance with the same people as one of the already registered participants. For simplicity, the participants signing up are numbered with consecutive natural numbers starting from 1. Initially, participants numbered 1 and 2 are registered, and they can dance with each other.

Bajtazar has already written a program that will allow pairing up participants. For his program to work correctly, Bajtazar needs to find out from time to time how many people a specified participant can dance with. Your task is to write a program that will help Bajtazar answer such queries.

Input

The first line of input contains an integer $q$ ($1 \le q \le 1\,000\,000$) representing the number of actions to process. Each of the following $q$ lines is in one of the following formats:

• $W \ x$ – denotes the arrival of a new picky person (with the next consecutive number), who declares the possibility of dancing with the person numbered $x$;
• $Z \ x$ – denotes the arrival of a new jealous person (with the next consecutive number), who declares that among the already registered people, they can dance with the same people as the person numbered $x$;
• $? \ x$ – denotes a query to Bajtazar's program about how many people the person numbered $x$ can dance with at that moment (you may assume that Bajtazar's program will always ask at least one such query).

Output

The output should contain exactly as many lines as there were $?$ queries in the input. Subsequent lines should contain a single integer representing the answer to Bajtazar's program query.

Examples

Input 1

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

Output 1

1
2
3
2

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.