Time Travel

Hyunsu bought a time machine to get more coding practice time. At each step, Hyunsu does exactly one of the following:

1. Solve a problem as usual, without using the time machine.
2. Time-travel to some point in the past.

He can never travel to the future, and once he goes back to the past, a new future starts unfolding from that point.

Hyunsu records the problems he solves, in the order he solves them. When he travels to the past, only the problems recorded up to (but not including) that point remain in his list.

At every step, Hyunsu wants to know the number of the most recently solved problem in the list. If the list is empty, print $-1$.

Hyunsu processes $N$ ($1 \le N \le 80{,}000$) queries $Q_1, Q_2, \dots, Q_N$ in order along his timeline. Each query is given on its own line and starts with a character $c$ (one of 'a', 's', 't').

• If $c$ is 'a', it is followed by a space and an integer $K$ ($1 \le K \le 1{,}000{,}000$). Hyunsu solves problem number $K$ and appends it to the end of the list.
• If $c$ is 's', Hyunsu removes the most recently recorded problem from the list.
• If $c$ is 't', it is followed by a space and an integer $K$. Hyunsu time-travels to the state just before the $K$-th query is processed; that is, he returns to the list as it was after processing the first $K-1$ queries. Since he cannot travel to the future, $K$ is at most the number of the current query.

After processing each query $Q_i$, print the number of the most recently solved problem remaining in the list, or $-1$ if the list is empty.

For example, processing the queries 'a 5', 'a 8', 's', 't 2', 'a 9' in order changes the list as $[5] \to [5, 8] \to [5] \to [5] \to [5, 9]$, and the outputs are $5, 8, 5, 5, 9$. Here 't 2' returns to the state $[5]$, which is the list just before the 2nd query (i.e., after processing only the 1st query).

The first line contains the number of queries $N$.

Each of the next $N$ lines (from the 2nd line through the $(N+1)$-th line) contains one query $Q_i$. Each query has one of the forms 'a $K$', 's', or 't $K$'.

After processing each query $Q_i$, print the number of the most recently solved problem remaining in the list, one per line. If there is no such problem, print $-1$.