Маска подсетей

Рассмотрим компьютерную сеть с настроенной TCP/IP маршрутизацией. Будем рассматривать некоторую ее модификацию. А именно в этой сети находить N подсетей. Каждая подсеть характеризуется своей маской. Маска подсети представляет собой 4 однобайтных числа, разделенных точкой. Причем для масок выполнено следующее свойство: если представить маску в двоичном виде, то сначала она будет содержать k единиц, а потом q нулей, причем k + q = 32. Например, 255.255.255.0 — маска подсети, а 192.168.0.1 — нет.

Поясним, как получается двоичное представление IP-адреса. Для этого числа, составляющие IP-адрес, представляются в двоичной системе счисления (при этом каждое из них дополняется ведущими нулями до длины в 8 цифр), после чего удаляются точки. Получившееся 32-битное число и есть двоичное представление IP-адреса. Например, для адреса 192.168.0.1 этот процесс выглядит так: 192.168.0.1 → 11000000.10101000.00000000.00000001 → 11000000101010000000000000000001. Таким образом, двоичным представлением IP-адреса 192.168.0.1 является 11000000101010000000000000000001.

Будем говорить, что два компьютера с IP₁ и IP₂ лежат в подсети, если IP₁ /\ Mask = IP₂ /\ Mask, где Mask — маска этой подсети, а /\ — операция побитового логического «и». IP компьютера представляет собой так же 4 однобайтных числа, разделенных точкой.

Вам даны M пар IP адресов компьютеров. Для каждой из них Вам надо определить, в скольких подсетях из заданных они лежат.

Входные данные

В первой строке входного файла INPUT.TXT записано число N — количество подсетей. В следующих N строках перечислены маски этих подсетей. В N + 2 строке находится число M (0 ≤ M ≤ 10000). В следующих M строках записаны пары IP адресов, разделенных пробелом.

Выходные данные

Для каждой пары IP адресов в отдельной строке выходного файла OUTPUT.TXT выведите количество подсетей, в которых лежат оба компьютера.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]