세탁소의 상쇄 표식

문제

한 세탁소에서는 옷에 필요한 작업을 영문자로 기록한 긴 작업 띠를 사용한다. 영문 대문자는 특정 작업을 추가하는 표식이고, 같은 알파벳의 소문자는 그 작업을 취소하는 표식이다. 예를 들어 B와 b는 같은 종류에 속하지만, B와 c는 서로 다른 종류에 속한다. 같은 종류의 대문자와 소문자가 붙어 있으면 작업 띠에서 두 표식을 함께 없앨 수 있다. 작업 띠를 정리하는 기계는 입력 문자열을 왼쪽부터 한 글자씩 읽는다. 기계에는 처음에 비어 있는 보관 문자열이 있다. 새 글자를 읽었을 때 보관 문자열이 비어 있지 않고, 마지막 글자가 새 글자와 같은 알파벳이면서 대소문자만 반대라면 마지막 글자를 지운다. 이때 새 글자도 보관하지 않는다. 그 밖의 경우에는 새 글자를 보관 문자열의 맨 뒤에 붙인다. 이 규칙은 취소 표식이 먼저 등장한 경우에도 똑같이 적용하므로 aA와 Aa는 모두 상쇄된다. 기계는 입력의 각 글자를 정확히 한 번씩 읽고 위 동작을 수행한다. 어떤 글자를 지운 뒤에 이미 읽은 글자를 다시 읽지는 않는다. 다만 마지막 표식이 없어지면 그 앞에 있던 표식이 새로운 마지막 표식이 되므로, 나중에 읽는 글자와 상쇄될 수 있다. 같은 대소문자의 글자 두 개는 같은 알파벳이어도 상쇄되지 않는다. 서로 다른 알파벳 역시 상쇄되지 않는다. 모든 글자를 처리한 뒤 보관 문자열에 남은 표식을 순서대로 출력하려고 한다. 남은 표식이 하나도 없다면 빈 줄 대신 정해진 단어 EMPTY를 출력한다. 작업 띠의 길이와 내용이 주어질 때 기계가 최종적으로 보관하는 문자열을 구하는 프로그램을 작성한다.

입력

첫째 줄에 작업 띠의 길이인 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 영문 대문자 A부터 Z와 영문 소문자 a부터 z로만 이루어져 있다.

출력

모든 글자를 처리한 뒤 보관 문자열에 남은 글자를 한 줄에 출력한다. 보관 문자열이 비어 있으면 EMPTY를 출력한다.

8
abBAcDdc

cc

6
xYyXzZ

EMPTY

5
AAaBC

ABC

출처: Devin.KR 자체 제작