천문대의 상쇄 필터

문제

산 위의 천문대는 관측 장치에 넣을 필터 명령을 한 줄의 문자열로 기록한다. 명령에는 영문 대문자와 소문자만 사용한다. 알파벳의 종류는 필터의 종류를 나타내며, 대문자는 해당 필터의 보정을 더하는 명령이고 소문자는 같은 필터의 보정을 되돌리는 명령이다. 예를 들어 Q와 q는 같은 종류의 서로 반대인 명령이다. 장치에는 명령을 저장하는 임시 기록이 있다. 처음에는 이 기록이 비어 있다. 관측 담당자는 주어진 문자열의 문자를 왼쪽부터 하나씩 읽어 임시 기록에 반영한다. 새 명령을 읽었을 때 임시 기록이 비어 있지 않고, 기록의 마지막 명령이 새 명령과 같은 알파벳이면서 대소문자가 서로 다르면 마지막 명령을 기록에서 지운다. 이때 새 명령도 기록에 추가하지 않는다. 그 밖의 경우에는 새 명령을 기록의 맨 뒤에 추가한다. 이 규칙에서 비교하는 대상은 항상 현재 임시 기록의 마지막 명령뿐이다. 앞쪽에 같은 종류의 명령이 있더라도 마지막 명령이 다른 종류라면 상쇄하지 않는다. 또한 대소문자까지 같은 두 명령은 상쇄하지 않는다. 한 명령의 처리가 끝난 뒤에는 다음 입력 명령으로 넘어가며, 이미 처리한 입력 문자를 다시 읽지 않는다. 모든 명령을 처리한 뒤 남아 있는 임시 기록이 실제 관측에 사용할 최종 명령열이다. 최종 명령열의 길이와 그 내용을 구해야 한다. 처음 주어진 명령열에는 적어도 한 문자가 있지만, 서로 반대인 명령들이 상쇄되어 최종 기록은 비어 있을 수도 있다. 이 경우에는 빈 문자열 대신 지정된 표시를 출력한다.

입력

첫째 줄에 명령열의 길이인 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 모든 문자는 영문 대문자 또는 영문 소문자이다.

출력

첫째 줄에 최종 명령열의 길이를 출력한다. 둘째 줄에 최종 명령열을 출력한다. 최종 명령열이 비어 있으면 둘째 줄에 EMPTY를 출력한다.

8
ABbaCcdE

2
dE

4
qQQq

0
EMPTY

5
AAaBb

1
A

출처: Devin.KR 자체 제작