게임 서버의 임시 효과 기록

문제

한 게임 서버는 시험 경기에서 발생한 임시 효과를 영문 소문자 하나로 표시한다. 같은 문자는 같은 종류의 효과를 뜻하며, 서로 다른 문자는 다른 종류의 효과를 뜻한다. 서버가 받은 효과 기록은 발생 순서대로 이어 붙인 문자열 S다. 서버는 이 기록을 왼쪽부터 한 글자씩 읽으면서, 최종적으로 보관할 임시 기록을 만든다. 처리를 시작하기 전의 임시 기록은 빈 문자열이다. 새 문자 c를 읽었을 때 임시 기록이 비어 있거나 임시 기록의 마지막 문자가 c와 다르면, 서버는 c를 임시 기록의 맨 뒤에 붙인다. 반대로 임시 기록의 마지막 문자가 c와 같으면, 마지막 문자 하나를 임시 기록에서 지우고 새로 읽은 c도 버린다. 같은 종류의 효과 두 개가 연속으로 맞닿으면 서로 상쇄되는 규칙이다. 한 문자를 처리할 때는 이 두 동작 중 정확히 하나만 수행한다. 상쇄로 인해 앞쪽 문자가 다시 임시 기록의 마지막 문자가 될 수 있다. 다음 입력 문자는 이렇게 바뀐 마지막 문자와 비교한다. 이미 읽은 원본 문자열의 위치로 돌아가서 처리하지 않으며, 원본에서 바로 앞에 있던 문자와 비교하는 것도 아니다. 판단 기준은 언제나 현재 임시 기록의 마지막 문자다. 상쇄된 효과는 이후 처리에 다시 등장하지 않는다. 서버는 모든 문자를 입력 순서대로 정확히 한 번씩 처리한다. 효과 문자의 알파벳 순서에 따른 정렬이나 임의의 위치에 있는 문자 삭제는 허용하지 않는다. 최종 임시 기록에 남은 문자들은 그 순서를 유지한 채 출력한다. 모든 효과가 상쇄되어 아무 문자도 남지 않았다면, 빈 줄 대신 대문자로 된 지정 문자열 EMPTY를 출력한다.

입력

첫째 줄에 문자열 길이를 나타내는 정수 N이 주어진다. 둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다.
1 ≤ N ≤ 200,000
S는 영문 소문자 a부터 z까지만 포함하며 공백은 포함하지 않는다.

출력

모든 문자를 처리한 뒤의 임시 기록을 한 줄에 출력한다. 임시 기록이 비어 있으면 EMPTY를 출력한다.

7
abccbad

d

8
abddbaee

EMPTY

9
abacddcef

abaef

출처: Devin.KR 자체 제작