Problem Description

Translated from COCI 2014/2015 Contest 3 T5 “STOGOVI”.

Mirko is playing with stacks. At the start of the game, he has an empty stack numbered $0$. In step $i$ of the game, he chooses an existing stack numbered $v$, makes a copy of it, and then performs one of the following operations:

1. Push the number $i$ onto the top of the new stack.

2. Pop (delete) the number on the top of the new stack.

3. Choose another stack numbered $w$, and count how many distinct numbers appear in both the new stack and stack $w$.

The newly created stack is numbered $i$.

Mirko does not like simulating this process with stacks by himself, so he wants you to write a program to carry it out. For each pop operation, output the deleted number, and for each counting operation, output the result.

Input Format

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

The steps of the game are numbered by the first $N$ integers in chronological order.

Each of the next $N$ lines describes step $i$ in one of the following three formats:

• a v, meaning a push operation.

• b v, meaning a pop operation.

• c v w, meaning a counting operation.

All indices involved in an operation are guaranteed to be in $[0, i - 1]$.

It is guaranteed that no pop operation will be applied to an empty stack.

Output Format

For each pop or counting operation, output one line containing the requested number, in the order of operations given in the input file.

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

2
1
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

2
2
8
8

Hint

Sample Explanation 1

At the start, we have the stack $S_0 = \{\}$.

In the first step, we copy $S_0$ and push the number $1$ onto the top, so $S_1 = \{1\}$.

In the second step, we copy $S_1$ and push the number $2$ onto the top, so $S_2 = \{1,2\}$.

In the third step, we copy $S_2$ and pop the number $2$, so $S_3 = \{1\}$.

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

In the fifth step, we copy $S_4$ and pop the number $2$, so $S_5 = \{1\}$.

Translated by ChatGPT 5