뒤섞인 병원 예약 변경 기록

문제

한 병원의 예약 서버가 점검을 마치고 여러 저장 장치에 나뉘어 있던 변경 로그를 모았다. 저장 장치에서 가져온 순서가 서로 달라서, 입력에 먼저 나타나는 로그가 실제로 먼저 처리된 변경이라는 보장은 없다. 운영 담당자는 이 로그만으로 현재 유효한 예약을 복원하여 진료과별 예약 수를 확인하려 한다. 로그 한 줄에는 변경 순번, 예약 번호, 진료과 번호, 상태가 기록되어 있다. 변경 순번은 서버가 변경을 처리할 때 붙인 정수이다. 서로 다른 로그의 변경 순번은 모두 다르며, 순번이 클수록 나중에 처리된 변경이다. 같은 예약 번호의 로그가 여러 줄 존재할 수 있다. 예약 번호가 같으면 진료과가 바뀌었더라도 하나의 예약으로 취급한다. 상태 A는 예약이 활성 상태임을 뜻하고, 상태 C는 예약이 취소 상태임을 뜻한다. 각 로그는 이전 로그에 일부 정보를 덧붙이는 기록이 아니라, 그 변경 직후 예약의 진료과와 상태를 모두 나타내는 기록이다. 따라서 예약마다 변경 순번이 가장 큰 로그 하나만 현재 상태를 결정한다. 취소된 예약이 나중에 다시 활성 상태가 되는 것도 가능하다. 현재 상태가 A인 예약은 마지막 로그에 적힌 진료과의 예약 수에 정확히 하나를 더한다. 현재 상태가 C인 예약은 어느 진료과에도 더하지 않는다. 로그에 등장하지 않은 예약은 집계 대상이 아니다. 일부 예약의 첫 로그가 C여도 정상적인 입력이며, 그보다 앞선 기록을 추측할 필요는 없다. 진료과 번호는 1번부터 D번까지이다. 모든 진료과의 현재 활성 예약 수를 번호 순서대로 출력하고, 그 수가 가장 큰 진료과 번호도 출력한다. 최대 예약 수가 같은 진료과가 여러 개이면 번호가 가장 작은 진료과를 선택한다. 활성 예약이 하나도 없으면 선택한 진료과 번호로 0을 출력한다.

입력

첫째 줄에 로그 수 N과 진료과 수 D가 주어진다. 0 ≤ N ≤ 10,000, 1 ≤ D ≤ 100이다.
다음 N개 줄에는 변경 순번 S, 예약 번호 B, 진료과 번호 K, 상태 X가 공백으로 구분되어 주어진다. 변경 순번은 1부터 N까지가 각각 정확히 한 번씩 등장한다. 1 ≤ B ≤ 100,000, 1 ≤ K ≤ D이며, X는 대문자 A 또는 C이다. S, B, K는 정수이다. 로그의 입력 순서는 임의이다.

출력

첫째 줄에 1번부터 D번까지의 활성 예약 수를 공백으로 구분하여 출력한다. 둘째 줄에 선택한 진료과 번호를 출력한다. 활성 예약이 없으면 0을 출력한다.

6 3
2 11 1 A
5 12 2 C
1 12 1 A
6 11 3 A
4 13 2 A
3 11 2 C

0 1 1
2

3 2
3 7 2 C
1 7 1 A
2 8 1 C

0 0
0

0 1

0
0

출처: Devin.KR 자체 제작