관측 자료의 겹치는 전송 경로

문제

날씨 관측소의 네트워크 담당자는 관측 자료 전송 기록을 분석한다. 각 기록에는 자료를 보낸 장비의 IPv4 주소와 자료를 받을 서버의 목적지 포트 번호가 들어 있다. 담당자는 서로 다른 장비가 같은 전송 경로를 사용하는 일이 얼마나 자주 나타나는지 알아보려 한다. 이 분석에서는 IPv4 주소가 다르면 서로 다른 장비로 취급하며, 기록에 나타나지 않은 장비에 대해서는 생각하지 않는다. IPv4 주소는 0 이상 255 이하인 정수 네 개를 점으로 연결하여 나타낸다. 네 정수를 왼쪽부터 각각 8비트 이진수로 바꾸어 이어 붙이면 주소를 나타내는 32비트 값이 된다. 모든 기록에는 하나의 공통 접두사 길이 P가 적용된다. 두 주소의 맨 앞 P비트가 같으면 두 주소는 같은 서브넷에 속한다. P가 0이면 모든 주소가 같은 서브넷에 속하고, P가 32이면 주소가 완전히 같아야 같은 서브넷에 속한다. 서로 다른 두 기록이 같은 서브넷에 속하고 목적지 포트 번호도 같으면 전송 경로가 겹친다. 다만 같은 장비에서 반복해서 보낸 기록은 이번 분석의 대상이 아니므로, 두 기록의 IPv4 주소가 같으면 세지 않는다. 따라서 주소가 다른 두 기록만 겹치는 기록 쌍이 될 수 있다. 기록은 입력된 순서대로 1번부터 N번까지 번호가 붙는다. 조건을 만족하는 번호 쌍 (i, j) 중 i < j인 쌍의 수를 구한다. 내용이 같은 기록이 여러 번 나타나더라도 각각 별개의 기록이다. 예를 들어 한 장비의 기록이 두 개이고 다른 장비의 기록이 세 개이며 이들이 같은 서브넷과 포트를 사용한다면, 이 두 장비 사이에서 여섯 쌍을 센다. 기록 사이의 시간 간격은 고려하지 않는다.

입력

첫째 줄에 기록 수 N과 공통 접두사 길이 P가 공백으로 구분되어 주어진다. N은 1 이상 16,000 이하의 정수이고, P는 0 이상 32 이하의 정수다.
다음 N개 줄에는 IPv4 주소와 목적지 포트 번호가 공백으로 구분되어 주어진다. IPv4 주소의 각 부분은 0 이상 255 이하의 정수이며, 숫자 0 자체를 제외하면 앞에 불필요한 0이 붙지 않는다. 목적지 포트 번호는 1 이상 65,535 이하의 정수다.

출력

조건을 만족하는 기록 쌍의 수를 정수 하나로 출력한다. 해당하는 쌍이 없으면 0을 출력한다.

6 24
10.4.8.1 9000
10.4.8.2 9000
10.4.8.1 9000
10.4.8.3 8000
10.4.9.2 9000
10.4.8.3 9000

5

3 32
192.0.2.7 80
192.0.2.7 80
192.0.2.8 80

0

4 0
1.2.3.4 53
200.1.1.1 53
1.2.3.4 53
8.8.4.4 80

2

출처: Devin.KR 자체 제작