공유 자전거 접속 점검

문제

공유 자전거 운영 구역에는 자전거 단말의 상태 보고를 받는 중계기가 있다. 네트워크 담당자는 중계기 한 대의 설정과 여러 접속 요청을 받아, 설정에 맞는 요청만 골라내는 점검 도구를 만들고 있다. 이 도구는 실제 통신 성공 여부를 예측하지 않고 아래에 명시한 주소와 포트 조건만 확인한다. 중계기의 설정에는 기준 IPv4 주소 A, 접두사 길이 K, 허용 포트 구간의 양 끝 L과 U가 들어 있다. IPv4 주소는 0부터 255까지의 정수 네 개를 점으로 연결한 표기다. 각 정수를 8비트 이진수로 나타내고 왼쪽부터 이어 붙이면 총 32비트가 된다. 주소에서 왼쪽 K비트가 A의 왼쪽 K비트와 같으면 같은 서브넷에 속한다고 판단한다. K가 0이면 모든 주소가 같은 서브넷에 속하고, K가 32이면 A와 완전히 같은 주소만 해당한다. A의 나머지 비트에는 어떤 값이 들어 있어도 된다. 접속 요청 하나에는 단말의 IPv4 주소 X와 목적지 포트 P가 기록되어 있다. 요청이 통과하려면 X가 설정된 서브넷에 속하면서 동시에 L ≤ P ≤ U를 만족해야 한다. 구간의 양 끝 포트도 허용한다. 이 문제에서는 서브넷의 모든 주소를 검사 대상으로 사용한다. 따라서 흔히 네트워크 주소나 브로드캐스트 주소로 구분하는 주소도 같은 규칙으로 통과시킬 수 있으며, 별도로 제외하지 않는다. 접속 요청은 입력 순서대로 1번부터 N번까지 번호가 붙는다. 같은 주소와 포트가 여러 번 나타나면 각각 별개의 요청으로 센다. 하나의 요청이 통과해도 뒤의 요청을 검사하는 규칙이나 허용 포트 구간은 바뀌지 않는다. 포트가 다르다는 이유로 서브넷을 달리 판단하거나, 주소가 같다는 이유로 포트 검사를 생략해서는 안 된다. 모든 요청을 검사하여 통과한 요청의 개수와 그중 번호가 가장 작은 요청의 번호를 구한다. 통과한 요청이 하나도 없다면 개수와 번호를 모두 0으로 보고한다. 주소를 구성하는 수는 십진수이며, 0을 제외한 수에는 앞에 불필요한 0이 붙지 않는다.

입력

첫째 줄에 `A K L U`가 공백으로 구분되어 주어진다. A는 유효한 IPv4 주소이며, K, L, U는 정수다. 0 ≤ K ≤ 32, 1 ≤ L ≤ U ≤ 65,535다.
둘째 줄에 정수 N이 주어진다. 0 ≤ N ≤ 15,000이다.
다음 N개 줄에 요청의 IPv4 주소 X와 정수 포트 P가 공백으로 구분되어 주어진다. X는 유효한 IPv4 주소이고 1 ≤ P ≤ 65,535다. A와 모든 X의 각 구성 정수는 0 이상 255 이하이며, 0을 제외하면 앞에 0이 붙지 않는다.

출력

통과한 요청의 개수와 통과한 요청 중 가장 작은 요청 번호를 공백으로 구분하여 출력한다. 통과한 요청이 없으면 `0 0`을 출력한다.

172.21.10.77 24 4000 4010
5
172.21.10.0 4000
172.21.11.77 4005
172.21.10.255 4010
172.21.10.8 4011
172.21.10.77 4004

3 1

255.1.2.3 0 80 80
3
0.0.0.0 79
203.44.7.9 80
255.255.255.255 80

2 2

10.4.9.2 32 9000 9002
2
10.4.9.3 9000
10.4.9.2 9003

0 0

출처: Devin.KR 자체 제작