도서관 2

문제

독서를 좋아하는 비타로는 도서관에서 책을 빌려 읽기로 했다. 비타로의 집은 좁기 때문에, 바닥에는 책 $1$ 권 분량의 공간밖에 없다. 다만 높이는 충분하기 때문에, 비타로는 이 공간에 책을 쌓아서 관리하기로 했다.

비타로는 이제부터 $Q$ 번의 행동을 한다. $i$ ($1$ ≦ $i$ ≦ $Q$) 번째 행동은 문자열 $S_{i}$ 로 나타난다. $S_{i}$ 는 영어 소문자로 이루어진 문자열이거나 READ 중 하나이며, 그 의미는 다음과 같다.

• 영어 소문자로 이루어진 문자열인 경우, 비타로는 책 이름이 $S_{i}$ 인 책을 도서관에서 빌려, 공간의 맨 위에 쌓는다.
• READ 인 경우, 비타로는 공간의 맨 위에 쌓여 있는 책을 읽고, 도서관에 반납한다.

당신은 비타로가 어떤 책을 어떤 순서로 읽었는지 알고 싶다.

$Q$ 번의 행동의 내용이 주어졌을 때, 비타로가 읽은 책의 이름을 읽은 순서대로 출력하는 프로그램을 작성하시오.

제한

• $2 \le Q \le 200\,000$.
• $Q$ 는 정수이다.
• $S_{i}$ 는 길이 $1$ 이상 $10$ 이하의 문자열이다 ($1 \le i \le Q$).
• $S_{i}$ 는 영어 소문자로 이루어진 문자열 또는 READ 이다 ($1 \le i \le Q$).
• $S_{i}$ 가 READ 인 $i$ ($1 \le i \le Q$) 가 $1$ 개 이상 존재한다.
• $S_{i}$ 가 READ 일 때, 반드시 공간에 $1$ 권 이상의 책이 존재한다 ($1 \le i \le Q$) .

서브태스크

1. ($40$ 점) $Q \le 2\,000$.
2. ($60$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$Q$
$S_{1}$
$S_{2}$
$:$
$S_{Q}$

출력

표준 출력에, $S_{i}$ 가 READ 인 행동 각각에 대해, 비타로가 읽은 책의 이름을 순서대로 줄바꿈으로 구분하여 출력한다.

채점 관련 주의사항

모든 제출은 채점 시스템에서 채점된다.

제출된 소스 코드는, 서브태스크에 대응하는 모든 채점용 입력 데이터에 대해 올바른 결과를 반환했을 때, 그 서브태스크에 대해 정답으로 인정된다.

각 제출의 점수는, 제출된 소스 코드에 대해 정답으로 인정된 서브태스크의 점수의 합이다.

이 과제의 점수는, 이 과제에 대한 모든 제출의 점수의 최댓값이다.

현재 점수는 「제출 결과」 탭의 「나의 점수 현황」에서 확인할 수 있다.

예제 입력 1

7
joi
joig
ioi
READ
egoi
READ
READ

예제 출력 1

ioi
egoi
joig

이 예제에서 비타로는 다음과 같이 행동한다.

1. 책 이름이 joi 인 책을 공간에 쌓는다. 이때, 공간에 쌓여 있는 책의 이름은 joi 가 된다.
2. 책 이름이 joig 인 책을 공간에 쌓는다. 이때, 공간에 쌓여 있는 책의 이름은 위에서부터 순서대로 joig , joi 가 된다.
3. 책 이름이 ioi 인 책을 공간에 쌓는다. 이때, 공간에 쌓여 있는 책의 이름은 위에서부터 순서대로 ioi , joig , joi 가 된다.
4. 책 이름이 ioi 인 책을 읽고 반납한다. 이때, 공간에 쌓여 있는 책의 이름은 위에서부터 순서대로 joig , joi 가 된다.
5. 책 이름이 egoi 인 책을 공간에 쌓는다. 이때, 공간에 쌓여 있는 책의 이름은 위에서부터 순서대로 egoi , joig , joi 가 된다.
6. 책 이름이 egoi 인 책을 읽고 반납한다. 이때, 공간에 쌓여 있는 책의 이름은 위에서부터 순서대로 joig , joi 가 된다.
7. 책 이름이 joig 인 책을 읽고 반납한다. 이때, 공간에 쌓여 있는 책의 이름은 joi 가 된다.

따라서 비타로가 읽은 책의 이름 ioi , egoi , joig 를 순서대로 줄바꿈으로 구분하여 출력한다.

이 예제는 모든 서브태스크의 제약을 만족한다.

예제 입력 2

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

예제 출력 2

one
seven
nine
eleven
ten
twelve
eight
six

이 예제는 모든 서브태스크의 제약을 만족한다.