G. DHCP troubles
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

...Во время межпланетных сборов программистов в институте Космической Гавани на планете Латакония случилось непредвиденное: в предназначенной для участников сборов подсети обнаружилась нехватка свободных IP-адресов. Прибывший с Земли системный администратор Дмитрий просканировал логи роутера, обнаружил список адресов подключенных устройств и поручил Вам по маске подсети и списку встречающихся в логе подключения адресов выяснить, сколько адресов в данной подсети свободно. Заметим, что роутер обслуживает не только интересующую нас подсеть, а также что один и тот же адрес может упоминаться в логах многократно.

Подсеть задаётся базовым IP-адресом и маской подсети.

  • Базовый IP-адрес представляет собой 32-битовое целое число и задаётся как набор из 4 целых чисел от 0 до 255 включительно, записываемых через точку (например, "129.1.3.17"). Первое число соответствует старшему байту ip-адреса, последнее — самому младшему. То есть записи "129.1.3.17" соответствует двоичное число 10000001 00000001 00000011 00010001.
  • Маска подсети M представляет собой целое число от 0 до 31 и обозначает количество старших бит IP-адреса, являющихся постоянными для всех адресов в данной подсети. То есть адрес принадлежит данной подсети тогда и только тогда, когда старшие M бит адреса и маски подсети совпадают.

    Маска подсети записывается через наклонную черту сразу после базового адреса. Например, "129.1.3.17/28". В данном случае маска равна 28, то есть подсеть включает в себя все IP-адреса с фиксированными 28 старшими битами 10000001 00000001 00000011 0001 (то есть адреса от "129.1.3.16" до "129.1.3.31" ).

  • При этом существуют два специальных IP-адреса, которые не могут быть назначены: наибольший адрес (где в маске нулевые биты — в нём стоят единицы) соответствует широковещательному адресу, наименьший — адресу самой подсети (где в маске нулевые биты — в нём стоят нулевые биты). В случае с подсетью "129.1.3.17/28" это адреса "129.1.3.16" и "129.1.3.31", тем самым до подключения первого устройства всего в этой подсети доступны 14 адресов.
Входные данные

Первая строка входных данных. задаёт подсеть в формате, описанном в условии задачи. Все числа в IP-адресе и маска подсети не содержат в записи ведущих нулей.

Во второй строке входных данных задано одно целое число N (1 ≤ N ≤ 100) — количество устройств, подключенных к роутеру. Каждая из последующих N строк содержит один IP-адрес, записанный в стандартном формате — упоминание подключенного к роутеру устройства в логе. Гарантируется, что все IP-адреса корректны.

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

Выведите одно целое число — количество свободных IP-адресов в заданной подсети. В случае, если в логах роутера обнаружены адрес или широковещательный адрес заданной подсети, то в конфигурации системы есть какая-то ошибка и надо вывести  - 1.

Примеры
Входные данные
129.1.3.17/28
2
129.1.3.17
129.1.3.15
Выходные данные
13
Входные данные
129.1.3.17/24
4
129.1.3.255
127.0.0.1
129.1.3.18
129.1.3.255
Выходные данные
-1