STOGOVI - Mirko's Stacks Game

Mirko is playing a stack game. Initially, there is a single empty stack with index \(0\). For every step \(i\) (\(1 \leq i \leq n\)), Mirko selects an existing stack with index \(v\) (guaranteed to exist), clones it, and then performs one of the following operations on the new copy:

• Push Operation (type 1): Push the number \(i\) onto the top of the new stack.
• Pop Operation (type 2): Remove the top element from the new stack and output the removed number.
• Query Operation (type 3): Given another stack with index \(w\) (guaranteed to exist), count how many distinct numbers appear in both the new stack and stack \(w\), and output this count.

After the operation, the new stack is assigned the index \(i\) and may be used in subsequent operations.

All numbers pushed are exactly the step number at which they are inserted. It is guaranteed that every pop operation is performed on a non-empty stack.

inputFormat

The first line contains an integer \(n\) representing the total number of operations.

Each of the next \(n\) lines describes an operation in one of the following formats:

• For a push operation: v 1
• For a pop operation: v 2
• For a query operation: v 3 w (where \(w\) is the index of another existing stack)

\(v\) and \(w\) are indices of stacks which have been created before the current step. The initial stack \(0\) is empty.

outputFormat

For each pop and query operation, output the result on a separate line. For a pop operation, output the removed number; for a query operation, output the number of distinct values that appear in both the new stack and the specified stack.

sample

5
0 1
1 1
2 2
1 3 0
3 3 2

2
0
1