자전거 거치대의 통신 묶음

문제

공유 자전거 운영팀의 네트워크 담당자는 거치대 제어 장치가 보낸 통신 기록을 정리하고 있다. 장치는 자신에게 설정된 IPv4 주소, 서브넷 접두사 길이, 목적지 포트를 기록한다. 담당자는 주소 설정이 올바르고 허용된 포트를 사용한 기록만 남긴 뒤, 같은 통신 설정에 해당하는 기록을 하나의 묶음으로 모으려고 한다. 같은 장치에서 반복해서 보낸 기록도 각각 한 건으로 센다. IPv4 주소는 0 이상 255 이하인 정수 네 개를 점으로 연결한 형태다. 주소 a.b.c.d의 정수값 X는 a×256³+b×256²+c×256+d다. 접두사 길이를 P라고 할 때 한 서브넷의 주소 수 B는 2의 (32-P)제곱이다. 이 기록의 네트워크 주소 정수값 A는 X를 B로 나눈 몫에 B를 곱한 값이며, 브로드캐스트 주소 정수값은 A+B-1이다. 이 문제에서는 각 기록에 적힌 접두사 길이로 그 기록의 서브넷을 독립적으로 계산한다. 주소 정수값 X가 네트워크 주소 A와 같거나 브로드캐스트 주소 A+B-1과 같으면 해당 기록을 제외한다. 또한 목적지 포트가 입력으로 주어진 허용 구간 L 이상 R 이하에 들어가지 않으면 제외한다. 두 제외 사유가 함께 나타나더라도 기록 하나를 제외하는 것으로 처리한다. 이 밖의 주소 종류나 실제 인터넷에서의 사용 여부는 판단하지 않는다. 남은 기록은 네트워크 주소 정수값 A, 접두사 길이 P, 목적지 포트의 세 값이 모두 같을 때 같은 묶음에 넣는다. 장치 주소 자체가 달라도 세 값이 같으면 같은 묶음이다. 네트워크 주소가 같더라도 접두사 길이나 목적지 포트가 다르면 서로 다른 묶음으로 취급한다. 중복 기록을 제거하지 않으므로 완전히 같은 입력 줄이 여러 번 나오면 그 횟수만큼 묶음의 기록 수가 증가한다. 담당자가 필요한 값은 만들어진 묶음의 개수와 한 묶음에 들어 있는 기록 수의 최댓값이다. 최댓값을 가진 묶음이 여러 개여도 그 수만 출력하면 되며 묶음을 따로 선택하지 않는다. 남은 기록이 하나도 없으면 두 값 모두 0으로 정한다. 주어진 통신 기록을 규칙에 따라 정리하여 두 값을 구한다.

입력

첫째 줄에 정수 N, L, R이 주어진다. 1 ≤ N ≤ 8,000, 1 ≤ L ≤ R ≤ 65,535이다. 다음 N개 줄에는 IPv4 주소, 정수 P, 정수 Q가 공백으로 구분되어 주어진다. P는 접두사 길이이고 Q는 목적지 포트다. 16 ≤ P ≤ 30, 1 ≤ Q ≤ 65,535이다. IPv4 주소의 각 부분은 0 이상 255 이하의 정수이며, 0을 제외하면 앞에 불필요한 0이 붙지 않는다.

출력

묶음의 개수와 한 묶음의 기록 수 최댓값을 공백으로 구분하여 한 줄에 출력한다. 모든 기록이 제외되면 0 0을 출력한다.

6 4000 5000
10.20.3.1 24 4500
10.20.3.200 24 4500
10.20.3.0 24 4500
10.20.3.255 24 4500
10.20.3.2 24 5001
10.20.4.1 24 4500

2 2

3 80 80
172.19.2.0 30 80
172.19.2.3 30 80
172.19.2.1 30 81

0 0

4 300 400
192.168.8.1 24 350
192.168.8.2 25 350
192.168.8.3 24 351
192.168.8.1 24 350

3 2

출처: Devin.KR 자체 제작