카페 레시피 보관대

문제

한 카페의 주문 시스템은 음료 제조기에 전달할 레시피를 임시 보관대에 저장한다. 레시피는 알파벳 대문자 A부터 Z까지로 구분하며, 같은 문자의 레시피가 보관대에 둘 이상 들어가는 일은 없다. 보관대에는 최대 K개의 레시피를 저장할 수 있다. 시스템 담당자는 하루 동안 남은 기록을 순서대로 재생하여 레시피를 새로 불러온 횟수와 공간 부족으로 내보낸 횟수를 확인하려 한다. 보관대는 앞에서 뒤로 순서가 있는 큐로 관리한다. 맨 앞은 가장 오래전에 사용한 레시피이고, 맨 뒤는 가장 최근에 사용한 레시피다. 기록을 처리하기 전에는 보관대가 비어 있다. 기록의 각 문자는 하나의 사건을 뜻하며, 왼쪽부터 오른쪽으로 처리한다. 대문자는 해당 음료의 주문을 뜻한다. 주문한 레시피가 이미 보관대에 있으면 그 레시피를 현재 위치에서 꺼내 맨 뒤로 옮긴다. 이때 새로 불러온 횟수는 증가하지 않는다. 주문한 레시피가 없으면 저장소에서 새로 불러오고, 새로 불러온 횟수를 1 증가시킨다. 이때 보관대에 이미 K개가 들어 있다면 맨 앞 레시피 하나를 먼저 내보내고, 공간 부족으로 내보낸 횟수를 1 증가시킨다. 그런 다음 주문한 레시피를 맨 뒤에 넣는다. 문자 '-'는 직원이 보관대를 정리한 사건이다. 보관대가 비어 있지 않으면 맨 앞 레시피 하나를 제거하고, 비어 있으면 아무 일도 일어나지 않는다. 정리로 제거한 레시피는 공간 부족으로 내보낸 횟수에 포함하지 않는다. 정리 사건은 새로 불러온 횟수에도 영향을 주지 않는다. 모든 사건은 기록에 나온 순서대로 하나씩 완료되므로 동시 처리나 동점은 없다. 전체 기록을 처리한 뒤 두 횟수와 보관대에 남은 레시피의 순서를 구해야 한다.

입력

첫째 줄에 보관대 용량 K와 사건 수 N이 공백으로 구분되어 주어진다. K와 N은 정수이며 1 ≤ K ≤ 26, 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 알파벳 대문자 A부터 Z까지 또는 '-'이며, 문자열 안에는 공백이 없다.

출력

첫째 줄에 레시피를 새로 불러온 횟수와 공간 부족으로 내보낸 횟수를 공백으로 구분하여 출력한다. 둘째 줄에 보관대의 맨 앞부터 맨 뒤까지 레시피 문자를 공백 없이 이어서 출력한다. 보관대가 비어 있으면 대신 '-' 하나를 출력한다.

3 9
ABACDB-EA

7 3
BEA

1 7
AA--B-B

3 0
B

2 4
AB--

2 0
-

출처: Devin.KR 자체 제작