Problem Description

Bitaro, who loves reading, decided to borrow books from the library and read them. Bitaro's house is small, so there is only enough space on the floor for one book. However, the height is sufficient, so Bitaro decided to manage the books by stacking them on this space.

Bitaro will take $Q$ actions. The $i$-th ($1 \leq i \leq Q$) action is represented by a string $S_i$. $S_i$ is either a string consisting of lowercase English letters or READ, and its meaning is as follows:

• If $S_i$ is a string consisting of lowercase English letters, Bitaro borrows a book with the title $S_i$ from the library and stacks it on top of the space.
• If $S_i$ is READ, Bitaro reads the book on top of the stack and returns it to the library.

You want to find out which books Bitaro read and in what order.

Given the details of $Q$ actions, create a program that outputs the titles of the books Bitaro read in the order he read them.

Input Format

The input is given from the standard input in the following format:

$Q$ $S_1$ $S_2$ $\vdots$ $S_Q$

Output Format

For each action where $S_i$ is READ, output the title of the book Bitaro read in the order they were read, separated by newlines.

Sample Input and Output

Sample Input #1

7
joi
joig
ioi
READ
egoi
READ
READ

Sample Output #1

ioi
egoi
joig

Sample Input #2

20
one
READ
two
three
four
five
six
seven
READ
eight
nine
READ
ten
eleven
READ
READ
twelve
READ
READ
READ

Sample Output #2

one
seven
nine
eleven
ten
twelve
eight
six

Notes/Hints

Constraints

• $2 \leq Q \leq 200,000$.
• $Q$ is an integer.
• $S_i$ is a string of length between $1$ and $10$ ($1 \leq i \leq Q$).
• $S_i$ is either a string consisting of lowercase English letters or READ ($1 \leq i \leq Q$).
• There is at least one $i$ ($1 \leq i \leq Q$) such that $S_i$ is READ.
• When $S_i$ is READ, there is always at least one book in the space ($1 \leq i \leq Q$).

Subtasks

1. ($40$ points) $Q \leq 2,000$.
2. ($60$ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the scores of the subtasks recognized as correct for that submission.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under "My Score Status" on the "Submission Results" tab.

Sample Explanation 1

In this input example, Bitaro acts as follows:
1. Stacks a book with the title joi on the space. The titles of the stacked books are joi.
2. Stacks a book with the title joig on the space. The titles of the stacked books are joig, joi from top to bottom.
3. Stacks a book with the title ioi on the space. The titles of the stacked books are ioi, joig, joi from top to bottom.
4. Reads and returns the book with the title ioi. The titles of the stacked books are joig, joi from top to bottom.
5. Stacks a book with the title egoi on the space. The titles of the stacked books are egoi, joig, joi from top to bottom.
6. Reads and returns the book with the title egoi. The titles of the stacked books are joig, joi from top to bottom.
7. Reads and returns the book with the title joig. The titles of the stacked books are joi.
Therefore, output the titles of the books read by Bitaro ioi, egoi, joig in order, separated by newlines. This input example satisfies the constraints of all subtasks.

Sample Explanation 2

This input example satisfies the constraints of all subtasks.

见题面 Input 部分

见题面 Output 部分