Чтобы управлять движением сетевых пакетов,
используются специальные устройства — маршрутизаторы. Поведение
маршрутизатора определяется таблицей маршрутизации. Эта таблица состоит из
нескольких строк, каждая из которых содержит IP-адрес сети назначения d,
маску m и IP-адрес шлюза g. Например, строка «192.168.24.0
255.255.255.0 192.168.14.1» означает, что пакет, адресованный в сеть
192.168.24.0 с маской 255.255.255.0, нужно отправить на шлюз 192.168.14.1.
IP-адрес представляет собой 32-битное число. Для удобства
он разбивается на четыре байта, каждый из них записывается в десятичном виде, а
между байтами ставятся точки. Так, IP-адрес 11000000101010000001100000000000
записывается как 192.168.24.0. Маски имеют такой же вид, при этом в двоичном
представлении маски сначала идут только единицы, а потом — только нули.
Когда на маршрутизатор приходит пакет, отправленный на
адрес a, маршрутизатор находит те строки таблицы, для которых
выполняется условие d and m = a and m (and —
операция побитового «и»). Затем он выбирает из них строку, количество единичных
битов в маске которой максимально, и отправляет пакет на записанный в этой
строке шлюз. Гарантируется, что для любого адреса назначения таких строк всегда
будет не более одной.
Назовём две таблицы маршрутизации эквивалентными,
если при их использовании пакет с любым адресом назначения будет отправлен на
один и тот же шлюз (либо не отправлен ни на какой шлюз). Например, таблицы из первого
примера (см. ниже) эквивалентны, а из второго - нет.
Напишите программу для сравнения двух таблиц
маршрутизации.
В первой строке входного файла записано целое число N
(от 1 до 100 000) — количество записей в первой таблице маршрутизации. Следующие
N строк содержат таблицу маршрутизации в описанном выше формате. Затем
записано целое число M (от 1 до 100 000) — количество записей во
второй таблице. Следующие M строк содержат вторую таблицу маршрутизации.
В первой строке выходного файла выведите слово YES или NO.
Пример
|
Поток ввода
|
Поток вывода
|
|
4
192.168.0.0
255.255.255.0 192.168.14.1
192.168.1.0
255.255.255.0 192.168.14.1
192.168.2.0
255.255.255.0 192.168.14.2
192.168.3.0
255.255.255.0 192.168.14.2
2
192.168.0.0
255.255.252.0 192.168.14.1
192.168.2.0
255.255.254.0 192.168.14.2
|
YES
|
|
1
192.168.0.0
255.255.255.0 192.168.14.1
2
192.168.0.0
255.255.255.0 192.168.14.1
172.16.0.0
255.255.0.0 172.16.0.1
|
NO
|
