택배 거점의 순간 최대 보관량

문제

한 택배 운영팀의 데이터 담당자는 여러 거점에서 전송한 보관 상태 기록으로 거점별 최대 보관량을 계산하려 한다. 기록은 CSV 형식이며, 각 행에는 택배 번호 parcel과 새 거점 번호 hub가 들어 있다. 거점 번호는 1부터 M까지이고, 택배 번호는 1부터 999까지다. 기록에 한 번도 나타나지 않은 택배도 포함하여, 처음에는 모든 택배가 어느 거점에도 보관되어 있지 않다. 각 행은 해당 택배의 새로운 보관 상태를 뜻한다. hub가 1 이상이면 그 택배는 해당 거점에 보관된다. 직전에 다른 거점에 있었다면 기존 거점에서 빠지고 새 거점에 들어간다. 어느 거점에도 없었다면 새 거점에만 들어간다. hub가 0이면 해당 택배는 모든 거점 밖에 있는 상태가 된다. 기존 거점에 있었다면 그 거점의 보관량만 하나 줄어든다. 통신 재전송 때문에 동일한 상태가 반복해서 기록될 수 있다. 이미 해당 거점에 있는 택배를 같은 거점에 보관한다고 기록하거나, 이미 거점 밖에 있는 택배에 대해 hub가 0인 기록을 받은 경우에는 보관량이 바뀌지 않는다. 한 택배가 동시에 두 거점에 보관되는 일은 없다. 다른 거점으로 옮기는 행은 하나의 상태 변경으로 처리하며, 그 행의 처리가 끝난 뒤 보관량을 확인한다. CSV 행의 순서는 상태 변경 순서다. 별도의 시각 필드는 없으며, 행을 택배 번호나 거점 번호순으로 다시 정렬해서는 안 된다. 각 거점에 대해 처음 상태와 모든 행을 처리한 직후 상태 중 가장 큰 보관량을 구한다. 마지막 보관량이 아니라 기록 전체에서의 최댓값이 필요하다. 한 번도 택배가 보관되지 않은 거점의 최댓값은 0이다.

입력

첫째 줄에 정수 N과 M이 공백으로 주어진다. 1 ≤ N ≤ 50,000, 1 ≤ M ≤ 20이다.
둘째 줄에는 CSV 헤더 `parcel,hub`가 주어진다.
이후 N개 줄에는 `parcel,hub` 형식의 데이터 행이 주어진다. parcel은 1 이상 999 이하의 정수이며, hub는 0 이상 M 이하의 정수다. 각 필드는 앞에 불필요한 0이 없는 십진수 표기이며, 필드 사이에는 쉼표 하나만 있다. 공백, 따옴표, 빈 필드는 없다.

출력

거점 번호가 작은 순서대로 M개 줄을 출력한다. 각 줄에 거점 번호와 그 거점의 최대 보관량을 공백으로 구분하여 출력한다. 최대 보관량이 같은 거점도 모두 출력하며, 택배를 보관한 적이 없는 거점은 0을 출력한다.

8 3
parcel,hub
11,1
12,1
11,1
11,2
12,0
13,2
11,0
13,3

1 2
2 2
3 1

5 2
parcel,hub
7,0
7,0
9,0
7,0
9,0

1 0
2 0

5 2
parcel,hub
1,1
2,1
1,2
2,2
1,1

1 2
2 2

출처: Devin.KR 자체 제작