순환 버스의 남은 줄

문제

한 버스 노선은 S개의 정류장을 원형으로 연결한다. 버스는 1번 정류장부터 출발하여 2번, 3번 순서로 방문하고, S번 다음에는 다시 1번을 방문한다. S가 1이면 같은 정류장을 계속 방문한다. 운행 기록에는 버스가 정류장에 도착한 사건이 시간순으로 K개 적혀 있다. 첫 번째 사건의 정류장은 반드시 1번이며, 이후의 정류장은 노선 순서로 결정된다. 처음에는 버스 안에 승객이 없고 모든 정류장의 대기 인원도 0명이다. 버스의 정원은 C명이다. 각 방문 기록에는 내리려고 하는 인원 A와 해당 정류장에 새로 도착한 인원 B가 적혀 있다. 기록을 처리할 때에는 먼저 버스 안의 승객 중 A명이 내린다. 다만 버스 안에 A명보다 적은 승객이 있으면 현재 승객이 모두 내린다. 내린 승객은 정류장의 대기 줄에 합류하지 않고 이동을 마친다. 그다음 새로 도착한 B명이 해당 정류장의 기존 대기 줄에 합류한다. 버스는 남은 좌석 수와 현재 대기 인원 중 작은 수만큼의 승객을 태운 뒤 출발한다. 좌석이 부족해서 타지 못한 사람은 그 정류장에 그대로 남아 다음 방문을 기다린다. 다른 정류장의 대기 인원은 이번 방문으로 바뀌지 않는다. 방문 기록 사이에 별도로 도착하거나 대기를 포기하는 사람은 없다. 정류장마다 대기 인원을 따로 관리해야 하며, 한 정류장을 다시 방문하면 이전에 남겨 둔 인원에 새 도착 인원을 더해야 한다. 각 기록은 반드시 내리기, 대기 줄 합류, 타기의 순서로 처리한다. K개의 기록을 모두 처리한 직후 버스 안의 승객 수, 지금까지 버스에 탄 누적 인원수, 모든 정류장에 남은 대기 인원의 합을 구해야 한다. 누적 탑승 인원에는 방문마다 실제로 탄 인원을 더한다.

입력

첫째 줄에 정수 S, C, K가 공백으로 주어진다. 1 ≤ S ≤ 10000, 1 ≤ C ≤ 10000, 1 ≤ K ≤ 20000이다.
다음 K개 줄에 각 방문의 정수 A와 B가 시간순으로 주어진다. 0 ≤ A, B ≤ 9999이다.
i번째 방문의 정류장 번호는 ((i-1)을 S로 나눈 나머지)+1이다. i는 1부터 K까지의 정수다.

출력

모든 방문을 처리한 직후의 버스 안 승객 수, 누적 탑승 인원수, 모든 정류장의 대기 인원 합을 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 각 값이 0이면 0을 그대로 출력한다.

2 3 4
0 5
1 2
2 1
3 0

1 7 1

1 2 3
9 4
1 0
5 0

1 4 0

3 5 2
0 0
7 0

0 0 0

출처: Devin.KR 자체 제작