농장 센서망의 점검 대상

문제

여러 온실을 운영하는 농장의 네트워크 담당자는 센서 수집 서버에 도착한 접속 기록을 점검한다. 기록에는 접속한 장치의 IPv4 주소와 서버에서 사용한 목적지 포트가 남아 있다. 이번 점검에서는 지정된 서브넷에 속하면서 지정된 포트 구간으로 접속한 장치만 확인한다. 같은 장치가 여러 번 접속했을 수 있으므로 조건을 만족하는 기록 수와 서로 다른 장치 수를 구분해야 한다. IPv4 주소는 0 이상 255 이하의 정수 네 개를 점으로 연결한 형식이다. 주소 `a.b.c.d`를 정수로 나타내면 a×256³+b×256²+c×256+d가 된다. 이 정수를 앞쪽부터 읽는 32자리 이진수로 보았을 때, 앞의 p개 비트가 기준 주소 A의 앞의 p개 비트와 같은 주소들이 이번 점검의 서브넷을 이룬다. p가 0이면 모든 주소가 같은 서브넷에 속하고, p가 32이면 기준 주소와 완전히 같은 주소만 속한다. 기준 주소 A의 뒤쪽 32-p개 비트가 모두 0이라는 보장은 없다. 서브넷을 판단할 때는 앞의 p개 비트만 사용한다. 또한 이 문제에서는 서브넷의 첫 주소와 마지막 주소도 일반 장치 주소와 똑같이 취급하며, 별도로 제외하지 않는다. 입력에 나타나는 각 주소는 표기 방식이 통일되어 있다. 점검할 포트의 범위는 두 정수 L과 R로 주어진다. 목적지 포트가 L 이상 R 이하일 때만 포트 조건을 만족한다. 장치는 IPv4 주소 하나로 식별하며, 서로 다른 포트를 사용했어도 주소가 같으면 같은 장치다. 어떤 주소에 대해 조건을 만족하는 접속 기록이 하나라도 존재하면 그 장치를 한 번 센다. 서브넷 조건과 포트 조건을 모두 만족하는 서로 다른 장치의 수를 구해야 한다. 어느 기록도 두 조건을 함께 만족하지 않으면 답은 0이다.

입력

첫째 줄에 접속 기록 수 N이 주어진다. 1≤N≤10,000이다. 둘째 줄에 기준 IPv4 주소 A와 접두사 길이 p가 공백으로 구분되어 주어진다. 0≤p≤32이다. 셋째 줄에 정수 L, R이 주어지며 1≤L≤R≤65,535이다. 다음 N개 줄에 IPv4 주소와 목적지 포트가 공백으로 구분되어 주어진다. 모든 주소의 각 부분은 0 이상 255 이하의 정수이며, 0 자체를 제외하고 앞에 불필요한 0이 없다. 모든 목적지 포트는 1 이상 65,535 이하의 정수다.

출력

두 조건을 모두 만족하는 서로 다른 IPv4 주소의 수를 정수 하나로 출력한다.

6
10.4.7.99 24
4000 4002
10.4.7.1 4000
10.4.7.1 4002
10.4.7.255 4001
10.4.8.1 4001
10.4.7.2 3999
10.4.7.0 4002

3

3
192.168.8.17 32
80 80
192.168.8.17 81
192.168.8.18 80
192.168.8.17 79

0

3
255.1.2.3 0
1 65535
0.0.0.0 1
255.255.255.255 65535
0.0.0.0 20

2

출처: Devin.KR 자체 제작