캠핑장 인원 기록 정제

문제

캠핑장 데이터 담당자는 여러 관리 단말에서 수집한 숙박 인원 기록을 정제하려 한다. 캠핑장에는 1번부터 S번까지 번호가 붙은 구역이 있고, 분석 기간은 1일부터 D일까지이다. 한 구역에서 하루 동안 숙박할 수 있는 인원은 최대 6명이다. 원본 기록 한 줄에는 구역 번호 s, 날짜 d, 숙박 인원 c가 들어 있다. 단말의 입력 오류와 재전송 때문에 원본에는 잘못된 값이나 같은 구역과 날짜에 대한 여러 기록이 섞여 있다. 담당자는 먼저 각 줄의 유효성을 독립적으로 검사한다. 구역 번호가 1 이상 S 이하이고, 날짜가 1 이상 D 이하이며, 숙박 인원이 0 이상 6 이하인 기록만 유효하다. 세 조건 중 하나라도 만족하지 않으면 무효 기록이다. 무효 기록은 집계 대상에서 완전히 제외하며, 앞서 저장한 값을 지우거나 바꾸지 않는다. 유효한 기록은 원본에 나타난 순서대로 반영한다. 같은 구역과 날짜에 대한 유효 기록이 여러 개라면 가장 뒤에 나타난 기록의 숙박 인원을 최종값으로 사용한다. 인원 0도 유효한 최종값이며, 해당 구역과 날짜에 숙박자가 없다는 뜻이다. 최종값이 0으로 바뀌었다고 해서 그 기록 자체를 무효로 취급하지 않는다. 정제 작업의 품질과 결과를 확인하기 위해 네 가지 수치를 출력해야 한다. 첫째는 원본에서 유효한 줄의 수이고, 둘째는 무효인 줄의 수이다. 셋째는 최종 숙박 인원이 양수인 서로 다른 구역과 날짜 쌍의 수이며, 넷째는 모든 최종 숙박 인원의 합이다. 유효 기록이 한 번도 없는 구역과 날짜는 마지막 두 수치에 기여하지 않는다. 모든 기록이 무효인 경우에도 같은 형식으로 결과를 출력한다.

입력

첫째 줄에 정수 N, S, D가 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ S ≤ 100, 1 ≤ D ≤ 365이다.
다음 N개 줄에 정수 s, d, c가 주어진다. 원본 값의 범위는 0 ≤ s ≤ S+1, 0 ≤ d ≤ D+1, -1 ≤ c ≤ 7이다. 이 범위 안에서도 지문의 유효성 조건을 만족하지 않는 기록이 포함될 수 있다.

출력

유효한 줄의 수, 무효인 줄의 수, 최종 인원이 양수인 구역과 날짜 쌍의 수, 최종 인원의 합을 공백으로 구분하여 한 줄에 출력한다. 마지막 두 값에 해당하는 항목이 없으면 각각 0을 출력한다.

6 2 3
1 1 2
1 1 4
2 3 0
3 1 2
2 2 7
2 3 1

4 2 2 5

3 1 1
1 1 6
1 1 0
0 1 4

2 1 0 0

2 1 2
1 0 3
1 2 -1

0 2 0 0

출처: Devin.KR 자체 제작