창구의 서식 보관함

문제

어느 은행의 창구 시스템은 고객의 대기 순서와 자주 사용하는 업무 서식을 함께 관리한다. 고객은 접수할 때 자신에게 필요한 서식 번호 하나를 등록한다. 서식 번호는 1 이상 99 이하의 정수이며, 같은 서식을 사용하는 고객이 여러 명일 수 있다. 시스템 담당자는 하루 동안 기록된 사건을 순서대로 재생하여 서식 보관함이 얼마나 자주 활용되었는지 확인하려고 한다. 시스템에는 고객 대기열과 서식 보관함이 있다. 대기열에는 먼저 접수한 고객이 앞에 놓이며, 나중에 접수한 고객은 맨 뒤에 추가된다. 보관함에는 서로 다른 서식을 최대 K개까지 저장할 수 있다. 기록을 재생하기 전에는 대기열과 보관함이 모두 비어 있다. 각 사건은 정수 하나로 주어진다. 양의 정수 x는 서식 번호가 x인 고객 한 명이 접수했다는 뜻이다. 이때 고객을 대기열의 맨 뒤에 추가한다. 접수만으로는 보관함의 내용이나 서식의 저장 순서가 바뀌지 않는다. 정수 0은 창구가 다음 고객을 호출했다는 뜻이다. 대기열이 비어 있으면 빈 호출 횟수만 1 증가시킨다. 그렇지 않으면 맨 앞 고객 한 명을 대기열에서 꺼내고, 그 고객에게 필요한 서식을 확인한다. 필요한 서식이 보관함에 있으면 적중 횟수를 1 증가시킨다. 이미 있던 서식을 사용해도 보관함의 저장 순서는 바뀌지 않는다. 필요한 서식이 없으면 조회 횟수를 1 증가시키고 해당 서식을 보관함에 새로 저장한다. 이때 보관함이 이미 K개의 서식을 저장하고 있다면, 현재 보관함에 남아 있는 서식 중 가장 먼저 저장한 서식 하나를 제거한 뒤 새 서식을 저장한다. 제거했던 서식을 나중에 다시 저장하면 그때 새로 저장한 것으로 취급한다. 고객 처리가 끝나도 사용한 서식은 보관함에 남는다. 모든 사건을 처리한 뒤 적중 횟수, 조회 횟수, 빈 호출 횟수, 대기열에 남은 고객 수를 구한다. 기록이 끝난 뒤 남은 고객을 추가로 처리하지 않는다.

입력

첫째 줄에 보관함의 용량 K와 사건 수 N이 공백으로 구분되어 주어진다. K와 N은 정수이며 1 ≤ K ≤ 99, 1 ≤ N ≤ 100,000이다.
다음 N개 줄에 사건을 나타내는 정수 x가 하나씩 주어진다. 0 ≤ x ≤ 99이다. x가 0이면 호출 사건이고, 양수이면 해당 서식 번호를 등록한 고객의 접수 사건이다.

출력

적중 횟수, 조회 횟수, 빈 호출 횟수, 대기열에 남은 고객 수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 각 값은 음이 아닌 정수이며, 해당하는 사건이나 고객이 없으면 0을 출력한다.

2 14
1
2
0
0
1
0
3
0
1
0
0
2
2
0

1 5 1 1

1 7
0
7
7
0
0
8
0

1 2 1 0

3 4
9
9
4
9

0 0 0 4

출처: Devin.KR 자체 제작