학원의 짝 카드 정리

문제

한 학원에서는 수업이 끝날 때마다 연습 카드를 정리한다. 카드에는 영어 소문자가 정확히 하나 적혀 있으며, 같은 글자가 적힌 카드 두 장은 하나의 연습 묶음을 뜻한다. 담당자는 책상에 놓인 카드를 왼쪽부터 차례대로 확인하여, 정리가 끝난 카드 줄의 오른쪽 끝에 새 카드를 붙인다. 처음에 정리된 카드 줄은 비어 있다. 새 카드를 붙인 직후, 카드 줄의 마지막 두 장에 같은 글자가 적혀 있다면 그 두 장을 모두 없앤다. 글자가 다르거나 카드가 한 장뿐이라면 아무것도 없애지 않는다. 카드 두 장이 없어졌더라도 이미 처리한 카드를 다시 가져오지는 않으며, 다음 입력 카드의 차례로 넘어간다. 모든 입력 카드를 처리할 때까지 이 과정을 반복한다. 예를 들어 현재 정리된 카드 줄이 ab이고 다음 카드가 b라면, 새 카드를 붙여 abb를 만든 뒤 마지막 두 장을 없애므로 카드 줄은 a가 된다. 이어서 a가 들어오면 두 장이 다시 짝을 이루므로 카드 줄은 비게 된다. 반면 현재 카드 줄이 ab일 때 c가 들어오면 세 장이 그대로 남는다. 사라진 카드는 이후 과정에 영향을 주지 않는다. 정리가 끝난 카드의 순서는 바꿀 수 없으며, 같은 글자라도 서로 이웃하지 않았다면 없앨 수 없다. 따라서 처음 주어진 문자열에서 각 글자의 개수가 홀수인지 여부만으로는 남는 카드 줄을 결정할 수 없다. 반드시 주어진 순서대로 카드를 처리해야 한다. 처음 놓인 카드의 개수 N과 왼쪽부터 적힌 글자를 나타내는 문자열 S가 주어진다. 모든 카드를 처리한 뒤 남은 카드의 글자를 왼쪽부터 이어 붙인 문자열을 출력한다. 남은 카드가 한 장도 없다면 영어 대문자로 EMPTY를 출력한다. 입력 글자는 모두 소문자이므로 이 표시는 실제 카드 줄과 혼동되지 않는다.

입력

첫째 줄에 카드의 개수인 정수 N이 주어진다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다.
1 ≤ N ≤ 100,000이다. S는 영어 소문자로만 이루어지며 공백을 포함하지 않는다.

출력

모든 카드를 처리한 뒤 남은 문자열을 한 줄에 출력한다. 남은 카드가 없으면 EMPTY를 출력한다.

4
abba

EMPTY

7
cabbaed

ced

출처: Devin.KR 자체 제작