공연장 출입 로그 복원

문제

한 공연장의 백엔드 운영 담당자는 출입 단말에서 수집한 로그로 운영 보고서를 만들려 한다. 공연장에는 1번부터 G번까지의 출입구가 있다. 관객은 번호로 식별되며, 보고 대상 시간이 시작될 때에는 모든 관객이 공연장 밖에 있다. 관객은 들어온 출입구와 다른 출입구로 나가도 된다. 로그 한 줄은 시각, 출입구 번호, 관객 번호, 동작을 세로줄 문자 |로 구분한 형태이다. 동작 I는 입장 요청, O는 퇴장 요청이다. 단말이 같은 요청을 여러 번 보내거나 실제 상태와 맞지 않는 요청을 보낼 수 있으므로, 기록된 요청이 모두 유효한 것은 아니다. 현재 밖에 있는 관객의 입장 요청과 현재 안에 있는 관객의 퇴장 요청만 승인한다. 이미 안에 있는 관객의 입장 요청과 이미 밖에 있는 관객의 퇴장 요청은 무시한다. 무시한 요청은 관객 상태와 모든 집계 값을 바꾸지 않는다. 로그는 시각이 감소하지 않는 순서로 주어진다. 시각이 같더라도 여러 요청을 한꺼번에 처리하지 않고, 입력에서 먼저 나온 요청부터 하나씩 처리한다. 승인한 입장 요청 직후에는 관객이 안에 있는 것으로 바뀌고, 승인한 퇴장 요청 직후에는 밖에 있는 것으로 바뀐다. 같은 관객이 여러 번 입장하고 퇴장하는 것은 허용된다. 보고서에는 세 가지 결과가 필요하다. 첫째는 무시한 요청의 총개수이다. 둘째는 요청을 하나씩 처리한 직후를 기준으로 한 공연장 내부 인원의 최댓값과, 그 최댓값에 처음 도달한 로그의 시각이다. 한 번도 입장이 승인되지 않았다면 이 결과는 0과 -1이다. 셋째는 승인한 입장 요청이 가장 많은 출입구 번호와 그 승인 횟수이다. 같은 관객의 재입장도 별도의 승인 횟수로 센다. 최다 횟수가 같은 출입구가 여러 개이면 번호가 가장 작은 출입구를 고른다. 승인한 입장 요청이 하나도 없으면 셋째 결과는 -1과 0이다. 주어진 로그를 순서대로 해석하여 이 보고서를 작성한다.

입력

첫째 줄에 로그 수 N과 출입구 수 G가 공백으로 주어진다. 두 값은 정수이며 1 ≤ N ≤ 30,000, 1 ≤ G ≤ 9이다.
다음 N개 줄에 t|g|u|a 형식의 로그가 주어진다. t, g, u는 선행 0이 없는 십진 정수이며, 값 0은 문자 0으로 쓴다. 0 ≤ t ≤ 999, 1 ≤ g ≤ G, 1 ≤ u ≤ 9,999이다. a는 대문자 I 또는 O이다. 각 줄에는 공백이 없으며 t는 입력 순서대로 감소하지 않는다.

출력

첫째 줄에 무시한 요청의 총개수를 출력한다. 둘째 줄에 내부 인원의 최댓값과 그 값에 처음 도달한 시각을 공백으로 구분하여 출력한다. 승인한 입장이 없으면 0 -1을 출력한다. 셋째 줄에 선정한 출입구 번호와 그 출입구의 입장 승인 횟수를 공백으로 구분하여 출력한다. 승인한 입장이 없으면 -1 0을 출력한다.

7 3
0|2|10|I
0|1|10|I
1|1|20|I
2|3|10|O
2|2|10|O
3|2|20|O
4|1|10|I

2
2 1
1 2

3 2
0|1|7|O
0|2|7|O
5|1|8|O

3
0 -1
-1 0

4 2
4|2|1|I
4|2|1|O
4|1|2|I
5|1|2|O

0
1 4
1 1

출처: Devin.KR 자체 제작