Stack Copying Game

Mirko is playing with stacks. When the game starts he has a single empty stack, numbered $0$. In step $i$ of the game he picks one of the stacks that already exist, calls its number $v$, copies that stack, and then does one of these three things.

1. Push the number $i$ onto the top of the copy.
2. Pop the number on top of the copy.
3. Pick one more stack, call its number $w$, and count how many distinct numbers sit in both the copy and stack $w$.

The stack he just created is numbered $i$.

Mirko does not want to handle the stacks himself, so write a program that does it for him. For every operation of type b, print the number popped off the stack. For every operation of type c, print how many numbers satisfy the condition.

The first line contains $N$, the number of steps in Mirko's game. ($1 \le N \le 300\,000$)

The steps of the game are numbered $1$ through $N$ in chronological order.

The $i$th of the next $N$ lines describes step $i$ in one of these three forms.

• "a v" for an operation of type a.
• "b v" for an operation of type b.
• "c v w" for an operation of type c.

The first character of the line gives the type of the operation. The one or two numbers after it are the stack labels the operation uses, and they are always integers in $[0, i-1]$.

For an operation of type b, the stack the element is popped from is not empty.

For every operation of type b and every operation of type c, print the number you computed, one per line, in the order the operations appear in the input.

Consider the first sample. At the start the only stack is $S_0 = \{\}$. Step 1 copies $S_0$ and pushes $1$ on top, so $S_1 = \{1\}$. Step 2 copies $S_1$ and pushes $2$ on top, so $S_2 = \{1, 2\}$. Step 3 copies $S_2$ and pops $2$, so $S_3 = \{1\}$. Step 4 copies $S_2$ and calls the copy $S_4$, then counts the numbers that appear in both $S_4$ and $S_3$. The only such number is $1$, so the answer is $1$. Step 5 copies $S_4$ and pops $2$, so $S_5 = \{1\}$.