천문대 관측망의 주소 구간

문제

천문대의 관측 장비들은 모두 10.42.A.B 형태의 IPv4 주소를 사용한다. 네트워크 담당자는 관측 도중 수집한 접속 기록에서 특정 목적지 포트로 향한 접속이 어느 서브넷에 모였는지 조사하려 한다. 기록에는 출발 장비의 주소와 목적지 포트가 들어 있으며, 접속 한 번마다 기록 한 줄이 남는다. 주소와 포트가 같은 기록이 반복되어도 서로 다른 접속으로 센다. 입력 파일의 크기를 줄이기 위해 주소의 마지막 두 옥텟 A와 B를 정수 X=256×A+B로 바꾸어 저장했다. A와 B는 각각 0 이상 255 이하이므로 X는 0 이상 65,535 이하다. 앞의 두 옥텟 10과 42는 모든 기록에서 같아 입력에 나타나지 않는다. 목적지 포트는 별도의 정수로 주어진다. 조사할 목적지 포트 T는 모든 질의에 공통으로 적용된다. 각 질의에는 주소를 나타내는 정수 X와 정수 K가 주어진다. 이 질의가 지정하는 서브넷은 전체 IPv4 주소에서 앞의 16+K개 비트가 X의 주소와 같은 주소들의 집합이다. 다시 말해 마지막 16비트 중 상위 K비트가 같은 주소들을 묶는다. 질의의 X가 서브넷의 가장 작은 주소일 필요는 없다. 구체적으로 W=2의 (16-K)제곱이라 하면 해당 서브넷의 주소 정수는 floor(X/W)×W 이상 floor(X/W)×W+W-1 이하다. K가 0이면 관측망 전체가 되고, K가 16이면 X 하나만 포함한다. 이 조사에서는 네트워크 주소나 브로드캐스트 주소를 따로 제외하지 않으며, 구간 안의 모든 주소를 같은 방식으로 취급한다. 각 질의마다 출발 주소가 지정한 서브넷에 속하고 목적지 포트가 T인 기록의 개수를 구한다. 조건에 맞는 기록이 없다면 그 질의의 답은 0이다.

입력

첫 줄에 정수 N, Q, T가 주어진다. N은 1 이상 10,000 이하인 기록 수이고, Q는 1 이상 10,000 이하인 질의 수다. T는 1 이상 65,535 이하인 목적지 포트다.
다음 N개 줄에 정수 X와 P가 주어진다. X는 0 이상 65,535 이하이고, 목적지 포트 P는 1 이상 65,535 이하다.
다음 Q개 줄에 정수 X와 K가 주어진다. X는 0 이상 65,535 이하이고 K는 0 이상 16 이하다. 입력에 등장하는 모든 수는 정수다.

출력

각 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다.

5 4 80
0 80
1 80
255 22
256 80
65535 80
17 8
300 8
65535 16
12345 0

2
1
1
4

3 3 443
100 22
100 22
101 80
100 16
100 15
0 0

0
0
0

4 3 9000
10 9000
10 9000
11 9000
12 9000
11 15
12 16
9 15

3
1
0

출처: Devin.KR 자체 제작