순서대로 호출하는 주차장

문제

한 주차장은 행사 차량을 맡아 보관하고, 진행 담당자의 호출에 맞춰 차량을 내보낸다. 주차 공간에는 1번부터 K번까지 서로 다른 번호가 붙어 있다. 처음에는 모든 공간이 비어 있으며, 각 공간에는 차량 한 대만 주차할 수 있다. 관리 프로그램은 시간순으로 전달되는 요청을 하나씩 처리한다. 요청은 입차 요청 A와 출차 호출 D의 두 종류다. 입차 요청 A가 들어오면 비어 있는 공간 중 번호가 가장 작은 공간에 새 차량을 주차한다. 비어 있는 공간이 없다면 해당 차량의 입차를 거절한다. 거절된 차량은 즉시 떠나며, 이후의 출차 호출 대상에도 포함되지 않는다. 한 번 거절한 입차를 나중에 다시 처리하지 않는다. 출차 호출 D가 들어오면 현재 주차된 차량 중 가장 먼저 입차한 차량 한 대를 내보낸다. 그 차량이 사용하던 공간은 즉시 비어 있는 공간이 되어 다음 요청부터 다시 사용할 수 있다. 현재 주차된 차량이 없다면 해당 호출은 아무 변화 없이 끝난다. 모든 요청은 주어진 순서대로 완전히 처리한 뒤 다음 요청을 처리하므로, 두 차량의 입차 순서가 같은 경우는 없다. 관리자는 요청 처리가 끝난 뒤 세 가지 값을 확인하려고 한다. 첫 번째 값은 성공한 입차의 총횟수이고, 두 번째 값은 거절된 입차의 총횟수다. 세 번째 값은 입차에 성공할 때마다 배정한 공간 번호를 모두 더한 값이다. 이 합에는 나중에 출차한 차량에 배정했던 번호도 포함한다. 같은 공간을 여러 차량이 차례로 사용했다면 그 번호를 사용 횟수만큼 더한다. 예를 들어 어떤 입차에 2번 공간을 배정했다면 번호 합에 2를 더한다. 이후 그 차량이 출차해도 이미 더한 값은 빼지 않는다. 거절된 입차와 출차 호출은 번호 합에 아무 값도 더하지 않는다. 모든 요청을 처리하여 세 값을 구하는 프로그램을 작성한다. 입차 요청이 한 번도 없으면 세 값은 모두 0이다.

입력

첫째 줄에 주차 공간 수 K와 요청 수 N이 공백으로 구분되어 주어진다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 A 또는 D이며, 왼쪽부터 요청을 처리한다.
K와 N은 정수이며 1 ≤ K ≤ 100,000, 1 ≤ N ≤ 100,000이다. 주차장이 가득 찼을 때의 A와 비어 있을 때의 D도 입력에 나타날 수 있다.

출력

성공한 입차 횟수, 거절된 입차 횟수, 성공한 입차에 배정한 공간 번호의 합을 이 순서대로 공백으로 구분하여 출력한다. 세 값은 모두 정수로 출력한다.

2 8
AAADAADA

4 2 6

3 5
DDDDD

0 0 0

3 8
AAADADAA

5 1 9

출처: Devin.KR 자체 제작