예약 거절 사유표

문제

한 병원은 특별 검진일의 예약 신청을 접수한다. 각 신청에는 환자 번호와 예약 칸 번호가 하나씩 적혀 있다. 예약 칸은 진료실과 시각을 함께 구분하는 번호이므로, 번호가 다른 두 칸은 서로 독립적이다. 환자 번호와 예약 칸 번호는 서로 다른 종류의 번호이며, 두 번호의 숫자가 같다는 사실에는 특별한 의미가 없다. 병원은 접수된 순서대로 신청을 하나씩 처리한다. 처음에는 확정된 예약이 없다. 한 환자는 검진일 전체에서 예약을 하나만 가질 수 있고, 한 예약 칸에는 환자를 한 명만 배정할 수 있다. 따라서 현재 환자에게 확정된 예약이 없고 신청한 칸도 비어 있을 때만 신청을 승인한다. 승인하면 해당 환자와 해당 칸을 연결한 예약이 즉시 확정된다. 확정된 예약은 이후 취소되거나 변경되지 않는다. 승인할 수 없는 신청은 거절하며, 그 사유를 세 종류로 나눈다. 환자에게 이미 예약이 있지만 신청한 칸은 비어 있으면 ‘환자 중복’이다. 환자에게 예약이 없지만 신청한 칸이 차 있으면 ‘칸 중복’이다. 환자에게 이미 예약이 있고 신청한 칸도 차 있으면 ‘양쪽 중복’이다. 마지막 경우에는 그 칸의 예약자가 신청한 환자 자신인지 다른 환자인지 구분하지 않는다. 거절된 신청은 어떤 예약도 만들지 않는다. 특히 환자 중복으로 거절된 신청에 적힌 빈 칸은 계속 비어 있고, 칸 중복으로 거절된 환자도 계속 예약이 없는 상태다. 같은 환자와 같은 칸이 적힌 신청이 여러 번 들어올 수 있으며, 이들 역시 각각 별개의 신청으로 처리한다. 나중에 들어온 신청을 먼저 처리하거나 앞선 처리 결과를 바꾸는 일은 없다. 모든 신청을 처리한 뒤 승인, 환자 중복, 칸 중복, 양쪽 중복으로 처리된 신청의 수를 각각 구해야 한다. 각 신청은 반드시 네 종류 중 정확히 하나에 포함된다. 어떤 종류에 해당하는 신청이 하나도 없다면 그 종류의 수는 0이다.

입력

첫째 줄에 신청 수 N이 주어진다.
다음 N개의 줄에는 접수 순서대로 환자 번호 P_i와 예약 칸 번호 S_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 25,000, 1 ≤ P_i ≤ 999,999, 1 ≤ S_i ≤ 999,999를 만족한다. 환자 번호와 예약 칸 번호는 각각 여러 신청에서 반복될 수 있다.

출력

승인된 신청 수, 환자 중복으로 거절된 신청 수, 칸 중복으로 거절된 신청 수, 양쪽 중복으로 거절된 신청 수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 해당하는 신청이 없는 종류는 0을 출력한다.

7
21 80
21 81
22 80
22 81
21 81
23 82
23 82

3 1 1 2

4
8 8
9 9
10 10
11 11

4 0 0 0

5
5 12
5 12
5 13
6 12
6 13

2 1 1 1

출처: Devin.KR 자체 제작