뒤집히는 알림 목록

문제

한 회사의 사내 메신저에는 아직 읽지 않은 알림 카드를 모아 두는 목록이 있다. 각 카드에는 알림의 종류를 나타내는 영어 소문자 하나가 적혀 있다. 같은 종류의 카드가 여러 장 들어올 수 있으며, 글자가 같더라도 각각 별개의 카드로 취급한다. 처음에는 목록이 비어 있다. 직원은 목록을 위에서 아래로 살펴본다. 새 알림이 도착하면 그 카드를 현재 목록의 맨 아래에 붙인다. 직원이 목록을 뒤집으면 현재 들어 있는 모든 카드의 위아래 순서가 반대가 된다. 뒤집기는 그 순간 존재하는 카드들의 순서만 바꾸는 작업이다. 따라서 목록을 뒤집은 뒤에 새 알림이 도착하더라도, 새 카드는 뒤집힌 목록의 맨 아래에 붙는다. 이후에도 같은 규칙을 계속 적용한다. 직원이 알림 하나를 읽으려고 하면 현재 목록의 맨 위 카드를 꺼낸다. 꺼낸 카드에 적힌 글자는 읽기 결과로 기록하며, 그 카드는 목록에서 사라진다. 목록이 비어 있을 때 읽기를 시도하면 아무 카드도 꺼내지 않고, 읽기 결과로 하이픈 한 개를 기록한다. 빈 목록이나 카드가 한 장인 목록을 뒤집어도 카드의 상태는 달라지지 않는다. 메신저의 작업 기록은 한 줄에 문자 하나로 주어진다. 영어 소문자는 해당 글자가 적힌 새 카드의 도착을 뜻하고, 느낌표는 목록 뒤집기를 뜻하며, 물음표는 알림 하나 읽기를 뜻한다. 작업은 입력에 나타난 순서대로 하나씩 수행한다. 여러 작업이 동시에 일어나는 경우는 없다. 모든 작업을 처리하면서 물음표 작업마다 기록되는 읽기 결과를 차례대로 구해야 한다. 읽지 않고 목록에 남겨 둔 카드의 내용은 출력하지 않는다. 물음표 작업이 한 번도 없다면 정해진 문자열 NONE을 출력한다.

입력

첫째 줄에 작업 수 N이 주어진다. N은 1 이상 100,000 이하인 정수다.
다음 N개의 줄에는 작업을 나타내는 문자 하나가 각각 주어진다. 각 문자는 영어 소문자 a부터 z 중 하나, 느낌표(!), 물음표(?) 중 하나다. 영어 소문자는 그 글자가 적힌 카드 한 장의 도착을 뜻한다. 작업 줄에는 다른 문자나 공백이 없다.

출력

물음표 작업이 있다면 각 작업의 읽기 결과를 작업 순서대로 한 줄에 하나씩 출력한다. 카드를 꺼냈다면 그 카드의 영어 소문자를 출력하고, 목록이 비어 있었다면 하이픈(-)을 출력한다. 물음표 작업이 하나도 없다면 NONE을 한 줄에 출력한다.

12
a
b
?
c
!
?
d
?
?
?
!
?

a
c
b
d
-
-

5
!
m
m
!
z

NONE

1
?

-

출처: Devin.KR 자체 제작