상영 조명 명령 정리

문제

한 영화관은 특별 상영에 사용할 조명 명령을 문자열로 관리한다. 조명에는 영문 알파벳으로 구분하는 26가지 효과가 있다. 대문자는 해당 효과를 켜라는 명령이고, 같은 알파벳의 소문자는 해당 효과를 끄라는 명령이다. 예를 들어 C와 c는 같은 효과에 대한 서로 반대인 명령이며, C와 d는 서로 다른 효과에 대한 명령이다. 이 문제에서는 실제 조명의 초기 상태나 명령 실행 가능 여부를 판단하지 않고, 문자열을 정리하는 규칙만 적용한다. 명령 기록을 정리할 때는 같은 효과에 대한 서로 반대인 명령 두 개가 바로 이웃하면 두 명령을 함께 삭제한다. 켜기 다음에 끄기가 나오거나 끄기 다음에 켜기가 나오는 경우 모두 삭제할 수 있다. 따라서 Aa와 aA는 삭제 대상이지만, AA와 aa는 삭제 대상이 아니다. 서로 다른 알파벳으로 된 두 명령도 삭제할 수 없다. 두 명령 사이에 다른 문자가 남아 있다면 두 명령은 이웃한 것이 아니다. 여러 삭제 위치 중 무엇을 먼저 고를지 혼동하지 않도록 정리 순서는 다음과 같이 정한다. 원본 문자열을 왼쪽부터 한 글자씩 읽고, 지금까지 정리한 문자열을 유지한다. 새로 읽은 글자가 정리한 문자열의 마지막 글자와 같은 효과의 반대 명령이면 마지막 글자를 지우고 새 글자도 남기지 않는다. 그렇지 않으면 새 글자를 정리한 문자열의 맨 뒤에 붙인다. 정리한 문자열이 비어 있다면 새 글자를 그대로 붙인다. 이 과정에서 앞서 떨어져 있던 명령들이 중간 명령의 삭제로 인해 이웃하게 될 수 있다. 예를 들어 aBCcbA를 차례로 처리하면 C와 c가 사라지고, 이어서 B와 b가 사라지며, 마지막으로 a와 A도 사라진다. 한 번 삭제한 명령은 다시 복원하지 않는다. 원본의 모든 글자를 정확히 한 번씩 위 규칙으로 처리한 뒤 남은 문자열을 구한다. 최종 문자열이 비어 있으면 빈 줄 대신 지정된 단어를 출력한다.

입력

첫째 줄에 원본 문자열의 길이인 정수 N이 주어진다. 1≤N≤200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 영문 대문자 A부터 Z 또는 영문 소문자 a부터 z다. 문자열에는 공백이 없다.

출력

정리 과정을 마친 뒤 남은 문자열을 한 줄에 출력한다. 남은 문자가 없으면 EMPTY를 출력한다. 출력 문자열의 대소문자는 남은 명령의 대소문자와 정확히 같아야 한다.

8
aBCcbAde

de

6
aBCcbA

EMPTY

7
AAaaBbc

c

출처: Devin.KR 자체 제작