주차 센서의 되감기 기록

문제

한 주차장은 여러 구역의 센서 신호를 하나의 문자열로 모아 저장한다. 구역은 영문 알파벳 26개로 구분한다. 대문자는 해당 구역에서 정방향 움직임을 감지한 신호이고, 소문자는 같은 구역에서 역방향 움직임을 감지한 신호이다. 예를 들어 G와 g는 같은 구역의 서로 반대 방향 신호이며, G와 h는 서로 다른 구역의 신호이다. 센서 점검 중에는 차량 대신 시험 장치가 앞뒤로 움직인다. 기록 담당자는 시험 장치가 바로 되돌아간 흔적을 없애기 위해 문자열을 왼쪽부터 한 글자씩 읽으며 다음 정리 규칙을 적용한다. 처음에는 정리된 기록이 빈 문자열이다. 새 신호를 읽었을 때 정리된 기록이 비어 있지 않고, 그 마지막 신호가 새 신호와 같은 구역의 반대 방향 신호라면 마지막 신호를 지우고 새 신호도 기록하지 않는다. 그렇지 않으면 새 신호를 정리된 기록의 끝에 붙인다. 대문자 뒤에 대응하는 소문자가 오는 경우와 소문자 뒤에 대응하는 대문자가 오는 경우 모두 지울 수 있다. 같은 방향의 두 신호는 지울 수 없다. 신호를 지운 뒤 과거에 읽었던 글자를 다시 읽지는 않지만, 이후의 새 신호는 삭제 결과로 드러난 마지막 신호와 비교한다. 따라서 앞부분에서 남아 있던 신호가 나중에 들어온 신호와 함께 지워질 수 있다. 이 규칙은 센서 기록을 정리하기 위한 것이므로 실제 주차 대수나 차량의 이동 가능성은 따로 검사하지 않는다. 주어진 문자열을 모두 읽은 뒤 남아 있는 기록을 원래의 순서대로 출력한다. 모든 신호가 지워졌다면 빈 문자열 대신 지정된 단어를 출력한다.

입력

첫째 줄에 신호 개수인 정수 N이 주어진다. 1≤N≤200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 영문 대문자 A부터 Z와 영문 소문자 a부터 z로만 이루어지며 공백은 없다.

출력

정리된 기록이 비어 있지 않으면 남은 문자열을 한 줄에 출력한다. 비어 있으면 EMPTY를 출력한다.

6
ABbaCc

EMPTY

7
aABcCBd

BBd

4
AAaa

EMPTY

출처: Devin.KR 자체 제작