상영표 편집 기록

문제

한 영화관에서는 로비 화면에 표시할 상영표를 편집하고 있다. 각 상영 안내 항목에는 영문 대문자 하나로 된 분류 코드가 붙어 있다. 편집 담당자가 기록한 문자열은 화면에 항목을 추가하려고 시도한 순서를 나타내며, 같은 분류의 항목도 여러 번 기록될 수 있다. 각 문자는 서로 구별되는 하나의 편집 기록이다. 이 편집기는 같은 분류를 연속으로 추가했을 때 두 항목을 함께 취소하는 기능을 사용한다. 처음 화면의 상영표는 비어 있다. 기록 문자열을 왼쪽부터 한 글자씩 읽으며 현재 글자의 코드를 처리한다. 화면이 비어 있으면 그 코드를 맨 뒤에 추가한다. 화면이 비어 있지 않고 맨 뒤 코드가 현재 코드와 다르면, 현재 코드를 맨 뒤에 추가한다. 화면의 맨 뒤 코드가 현재 코드와 같으면 동작이 달라진다. 이때는 화면의 맨 뒤 항목을 지우고, 현재 항목도 화면에 추가하지 않는다. 즉, 기존의 맨 뒤 항목 하나와 지금 처리하는 항목 하나가 함께 취소된다. 취소한 기록은 이후 처리에 다시 사용하지 않으며, 다음 입력 글자로 넘어간다. 화면에 남은 항목의 상대적인 순서는 언제나 유지된다. 취소로 인해 앞쪽에 있던 항목이 화면의 새로운 맨 뒤 항목이 될 수 있다. 따라서 입력 문자열에서 원래 이웃하지 않았던 두 기록도 나중에는 서로 취소될 수 있다. 예를 들어 기록이 ABBA이면 첫 A와 B가 추가된 뒤 다음 B가 기존 B를 지운다. 마지막 A는 화면에 남은 A를 지우므로 최종 화면은 비게 된다. 반면 ABAB는 처리하는 동안 같은 코드가 맨 뒤에서 만나지 않아 그대로 남는다. 담당자는 모든 기록을 처리한 뒤 화면에 실제로 남는 코드 목록을 확인하려 한다. 기록의 순서를 바꾸거나 취소 여부를 임의로 선택할 수 없으며, 반드시 위 동작을 각 글자에 한 번씩 적용해야 한다. 최종 화면의 코드를 앞에서부터 이어 붙여 출력한다. 모든 항목이 취소되어 화면이 비었다면, 빈 줄 대신 지정된 문자열 EMPTY를 출력한다.

입력

첫째 줄에 기록 문자열의 길이인 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 모든 문자는 영문 대문자 A부터 Z까지 중 하나이다.

출력

모든 기록을 처리한 뒤 남은 코드를 앞에서부터 이어 붙여 한 줄로 출력한다. 남은 코드가 없으면 EMPTY를 출력한다.

9
ACDDCBEEF

ABF

6
ABCCBA

EMPTY

5
ABABA

ABABA

출처: Devin.KR 자체 제작