It's movie night, and the theatre is packed with people. Indeed, the ticket booth is running to help the moviegoers process their tickets.

Every second, either one of two things happens to the line at the ticket booth:

1. \(S\): the moviegoer at the front of the line is served, and they leave the line
2. \(A_i\): a new moviegoer with ID \(i\) joins the end of the line

After \(N\) seconds, please tell us who is in the line (in order).

HINT: Use a deque! (a type of data structure)

Input Specification

The first line will contain the integer \(N\) (\(1 \le N \le 10^5\)).
The next \(N\) lines will contain either an operation type 1 (\(S\)) or an operation type 2 (\(A_i\)).

Output Specification

Print space-separated integers representing who is still in the line after \(N\) seconds.

Sample Input

4
A 1
A 2
S
A 3

Sample Output

2 3

Af \(1\) second, person \(1\) joins the line.
At \(2\) seconds, person \(2\) joins the line.
At \(3\) seconds, the first person in the line (person \(1\)) is served and so they leave.
At \(4\) seconds, person \(3\) joins the line.
After \(4\) seconds, the line is: \(2\) \(3\).