Mirko is playing with stacks. In the beginning of the game,
he has an empty stack denoted with number 0. In the
$i$-th step of the game he
will choose an existing stack denoted with $v$, copy it and do one of the
place number $i$ on
top of the new stack
remove the number from the top of the new stack
choose another stack denoted with $w$ and count how many different
numbers exist that are in the new stack and in the stack
denoted with $w$
The newly created stack is denoted with $i$.
Mirko doesn’t like to work with stacks so he wants you to
write a program that will do it for him. For each operation of
type (b) output the number removed from stack and for each
operation of type (c) count the required numbers and output how
many of them there are.
The first line of input contains the integer $N$ ($1
\leq N \leq 300\, 000$), the number of steps in Mirko’s
The steps of the game are chronologically denoted with the
first $N$ integers.
The $i$-th of the
following $N$ lines
contains the description of the $i$-th step of the game in one of the
following 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 in the line denotes the type of
operation and the following one or two denote the accompanying
stack labels that will always be integers from the interval
$[0, i - 1]$.
For each operation of type (b), the stack we are removing
the element from will not be empty.
For each operation type (b) or (c) output the required
number, each in their own line, in the order the operations
were given in the input.
|Sample Input 1
||Sample Output 1
c 2 3
|Sample Input 2
||Sample Output 2
c 4 5
c 8 7