Time-Traveling Cows

Farmer John recently purchased a time machine which allows him to manage his cow herd in a very unusual way. He performs \(N\) operations (where \(1 \leq N \leq 8 \times 10^4\)) and each operation is one of the following:

1. a x: Add a cow with label \(x\) (\(1 \leq x \leq 10^6\)).
2. s: Sell (remove) the most recently added cow. (It is guaranteed that there is at least one cow when this operation is performed.)
3. t x: Revert to the state before the \(x\)-th operation was executed. (It is guaranteed that the \(x\)-th operation exists.)

After each operation, output the label of the most recently added cow in the current state. If there are no cows, output \(-1\).

inputFormat

The first line contains a single integer \(N\), the number of operations.

Each of the next \(N\) lines contains one operation, which is either:

• a x
• s
• t x

It is guaranteed that all operations are valid as described in the problem.

outputFormat

For each operation, output on a new line the label of the most recently added cow after that operation, or \(-1\) if there is no cow.

sample

3
a 1
a 2
s

1
2
1