수족관 점검 접속 로그

문제

수족관 운영 서버는 수조별 점검 화면에 접속한 단말의 기록을 남긴다. 운영자는 로그를 읽어 각 수조의 누적 접속 시간과 최대 동시 접속 수를 구하려고 한다. 전송 오류로 상태에 맞지 않는 기록이 들어올 수 있으므로, 잘못된 기록을 무시하는 규칙까지 그대로 구현해야 한다. 로그 한 줄은 시각, 동작, 수조 번호, 단말 번호로 이루어진다. 동작 IN은 해당 단말이 해당 수조의 점검 화면에 접속한다는 뜻이고, OUT은 접속을 끝낸다는 뜻이다. 처음에는 모든 단말이 접속하지 않은 상태이다. 하나의 단말은 전체 수족관에서 동시에 하나의 수조에만 접속할 수 있다. IN 기록의 단말이 현재 어느 수조에도 접속하지 않았다면 그 기록을 처리하고 접속 시작 시각을 저장한다. 이미 어떤 수조에 접속 중이라면 수조 번호가 같더라도 그 IN 기록을 무시한다. OUT 기록은 해당 단말이 기록에 적힌 수조에 접속 중일 때만 처리한다. 접속하지 않은 단말의 OUT이나 다른 수조 번호가 적힌 OUT은 무시한다. 무시한 기록은 어떤 상태도 바꾸지 않으며, 무시한 기록 수만 1 증가시킨다. 처리한 OUT에 대해서는 종료 시각에서 저장된 시작 시각을 뺀 값을 해당 수조의 누적 접속 시간에 더한다. 여러 단말의 접속 시간이 겹치면 각각의 시간을 더한다. 모든 로그를 처리한 뒤에도 접속 중인 단말은 관찰 종료 시각 T에 접속을 끝낸 것으로 계산한다. 이 계산은 로그를 추가하거나 무시한 기록 수를 늘리지 않는다. 최대 동시 접속 수는 처음 상태와 각 로그 한 줄의 처리가 끝난 직후의 접속 수 중 최댓값이다. 같은 시각의 로그도 입력 순서대로 처리한다. 따라서 길이가 0인 접속도 최대 동시 접속 수에 영향을 줄 수 있다. 각 수조의 집계 결과와 전체에서 무시한 기록 수를 출력한다.

입력

첫째 줄에 수조 수 K, 로그 수 N, 관찰 종료 시각 T가 주어진다. 다음 N개 줄에는 정수 t, 문자열 A, 정수 b, 정수 d가 공백으로 구분되어 주어진다. 1 ≤ K ≤ 1,000, 1 ≤ N ≤ 12,000, 0 ≤ T ≤ 1,000,000,000이다. 0 ≤ t ≤ T이며 t는 입력 순서대로 감소하지 않는다. A는 IN 또는 OUT이고, 1 ≤ b ≤ K, 1 ≤ d ≤ 200,000이다. 모든 수치는 정수이다.

출력

수조 번호 1부터 K까지 순서대로 K개 줄을 출력한다. 각 줄에는 해당 수조의 누적 접속 시간과 최대 동시 접속 수를 공백으로 구분하여 출력한다. 접속 기록이 없는 수조의 두 값은 모두 0이다. 마지막 줄에는 무시한 기록 수를 출력한다.

2 7 10
1 IN 1 7
2 IN 2 7
3 IN 1 8
4 OUT 2 7
5 OUT 1 7
5 IN 2 7
8 OUT 1 8

9 2
5 1
2

1 4 0
0 OUT 1 3
0 IN 1 3
0 OUT 1 3
0 IN 1 3

0 1
1

출처: Devin.KR 자체 제작