Problem Description

Farmer John bought a time machine, which allows him to manage his herd of cows conveniently.

He now has $N$ operations ($1 \leq N \leq 8 \times 10^4$). Each operation is one of the following three types:

1. a x: Add a cow with ID $x$ ($1 \leq x \leq 10^6$).
2. s: Sell the most recently added cow (it is guaranteed that there is at least one cow at this time).
3. t x: Go back to the state before the $x$-th operation (it is guaranteed that the $x$-th operation exists).

After Farmer John performs each operation, output the ID of the newest cow he currently owns. In particular, if he has no cows, output $-1$.

Input Format

The first line contains an integer $N$.

The next $N$ lines each describe one operation.

Output Format

On the $i$-th line, output the ID of the newest cow Farmer John owns after the $i$-th operation. In particular, if he has no cows, output $-1$.

12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s

5
3
7
3
5
2
7
4
7
2
5
-1

Hint

Below is the explanation for the sample, where the owned cows are already listed in the order they were added.

Translated by ChatGPT 5