Problem Description

Translated from COCI 2014/2015 Contest 3 T5 "STOGOVI"

Mirko is playing with stacks. At the beginning of the game, he has an empty stack numbered $0$. During the $i$-th step of the game, he selects an existing stack numbered $v$ and performs one of the following operations by copying it:

1. Add the number $i$ to the top of the new stack.
2. Remove the number from the top of the new stack.
3. Select another stack numbered $w$ and count how many distinct numbers are present in both the new stack and stack $w$.

The newly created stack is numbered $i$.

Mirko dislikes simulating this process with stacks himself, so he wants you to write a program to execute this process. For each removal operation, output the removed number, and for each counting operation, output the result of the count.

Input Format

The first line contains an integer $N (1 \le N \le 300,000)$, representing the number of steps in the game.

The steps of the game are numbered sequentially with the first $N$ integers.

The following $N$ lines, where the $i$-th line describes the $i$-th step of the game, are in one of the following three formats:

• a v, indicating an add operation.
• b v, indicating a remove operation.
• c v w, indicating a count operation.

The numbers involved in the operations are guaranteed to be within the range $[0, i-1]$.

It is guaranteed that no remove operation will be performed on an empty stack.

Output Format

For each remove or count operation, output one line containing the requested number, in the order they appear in the input file.

Sample Input and Output

Sample Input #1

5
a 0
a 1
b 2
c 2 3
b 4

Sample Output #1

2
1
2

Sample Input #2

11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

Sample Output #2

2
2
8
8

Notes

Explanation of Sample 1

Initially, we have stack $S_0 = \{\}$.

In the first step, we copy $S_0$ and add the number $1$ to the top, resulting in $S_1 = \{1\}$.

In the second step, we copy $S_1$ and add the number $2$ to the top, resulting in $S_2 = \{1, 2\}$.

In the third step, we copy $S_2$ and remove the top number, $2$, resulting in $S_3 = \{1\}$.

In the fourth step, we copy $S_2$ and number it as $S_4$, then count how many distinct numbers are present in both $S_4$ and $S_3$. The only number present in both stacks is $1$, so the answer is $1$.

In the fifth step, we copy $S_4$ and remove the top number, $2$, resulting in $S_5 = \{1\}$.

见题面 Input 部分

见题面 Output 部分