농장 표찰의 겹침 정리

문제

한 농장은 수확 상자를 옮긴 순서대로 작물 표찰을 기록한다. 표찰 하나에는 알파벳 소문자 하나가 적혀 있으며, 같은 글자는 같은 종류의 작물을 뜻한다. 기록 담당자는 하루 동안 모은 표찰을 하나의 문자열로 만든 뒤, 농장에서 정한 겹침 정리 규칙에 따라 보관할 기록을 만든다. 정리는 원래 문자열의 왼쪽부터 오른쪽으로 표찰을 하나씩 읽으며 진행한다. 처음에는 보관 기록이 비어 있다. 새 표찰을 읽었을 때 보관 기록이 비어 있거나, 보관 기록의 마지막 글자가 새 표찰의 글자와 다르면 새 표찰을 보관 기록의 맨 뒤에 붙인다. 반대로 마지막 글자가 새 표찰의 글자와 같으면, 보관 기록의 마지막 표찰과 방금 읽은 새 표찰을 함께 없앤다. 이때 새 표찰을 보관 기록에 붙이지 않는다. 표찰 두 개가 없어지면 그 앞에 있던 표찰이 보관 기록의 마지막 표찰이 될 수 있다. 이후에 읽는 표찰은 이렇게 바뀐 마지막 표찰과 비교한다. 이미 읽고 없앤 표찰은 다시 사용하지 않으며, 원래 문자열에서 아직 읽지 않은 표찰의 순서도 바꾸지 않는다. 따라서 서로 다른 작물의 표찰을 건너뛰어 비교하거나, 정리가 끝난 뒤 임의의 두 표찰을 추가로 없애는 일은 없다. 예를 들어 앞에서 읽은 표찰이 없어졌더라도 그보다 먼저 보관한 표찰은 남아 있을 수 있다. 최종 결과는 없어지는 두 표찰의 수를 단순히 작물별로 세어서 구할 수 없으며, 표찰이 들어온 순서를 반영해야 한다. 모든 표찰을 정확히 한 번씩 읽은 뒤 보관 기록에 남은 표찰의 수와 그 문자열을 구한다. 남은 표찰이 하나도 없다면 빈 문자열 대신 지정된 단어를 출력한다.

입력

첫째 줄에 표찰의 수 N이 주어진다. N은 1 이상 200,000 이하의 정수다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 최종 보관 기록의 길이를 정수로 출력한다. 둘째 줄에 최종 보관 기록을 출력한다. 길이가 0이면 둘째 줄에 EMPTY를 출력한다.

8
abbaccad

2
ad

6
abccba

0
EMPTY

1
z

1
z

출처: Devin.KR 자체 제작