eolymp
bolt
Try our new interface for solving problems
Problems

Routing

Routing

Для определения маршрутов движения сетевых пакетов в современных сетях используются специальные устройства --- маршрутизаторы. В своих действиях маршрутизатор руководствуется таблицей маршрутизации. Такая таблица представляет набор строк, описывающих маршруты. Каждая строка содержит \textbf{3} поля --- \textbf{D}, \textbf{M} и \textbf{G}, где \textbf{D} --- IP-адрес сети назначения, \textbf{M} --- маска, \textbf{G} --- IP-адрес шлюза (заметим для точности, что в реальных таблицах полей больше). Например, строка \textbf{192.168.24.0 255.255.255.0 192.168.14.1} означает, что пакет, адресованный в сеть \textbf{192.168.24.0} с маской \textbf{255.255.255.0}, нужно отправлять через шлюз \textbf{192.168.14.1}. \textbf{Краткая справка}\textit{\textbf{.}} IP-адрес представляет собой \textbf{32}-битное число. Для удобства он записывается в десятично-точечном формате, то есть каждый байт представляется в десятичном виде, а между ними ставятся точки. Например, запись \textbf{192.168.24.0} означает двоичное число \textbf{11000000101010000001100000000000}. Это же верно и для масок. У масок есть важная особенность: в двоичном представлении маски всегда вначале идут только единицы, а потом --- только нули. Адрес шлюза не может состоять целиком из нулевых или единичных битов. Алгоритм выбора маршрута выглядит так. Пусть имеется пакет, адресованный на адрес \textbf{A}. Вначале маршрутизатор просматривает все записи и оставляет только те, где выполняется условие \textbf{D and M = A and M} (\textbf{and} --- операция побитового "\textbf{И}"). Затем уже из этих записей оставляется та, где количество единичных битов в маске максимально --- она и будет результатом. Гарантируется, что для любого адреса таких записей всегда будет не более одной. Чем больше размер таблицы, тем медленнее маршрутизатор работает и больше ресурсов потребляет. Но во многих случаях исходную таблицу можно преобразовать в эквивалентную ей, но содержащую меньше строк. Например, пусть первая таблица выглядит так: \textbf{192.168.0.0 255.255.255.0 192.168.14.1} \textbf{192.168.1.0 255.255.255.0 192.168.14.1} \textbf{192.168.2.0 255.255.255.0 192.168.14.2} \textbf{192.168.3.0 255.255.255.0 192.168.14.2} Вторая таблица выглядит так: \textbf{192.168.0.0 255.255.252.0 192.168.14.1} \textbf{192.168.2.0 255.255.254.0 192.168.14.2} Нетрудно убедиться, что для любого адреса назначения по этим двум таблицам определится один и тот же шлюз (либо никакой не определится). Заметим, что в данной задаче адресом назначения может быть любое \textbf{32}-битное число (то есть нет специальных и недопустимых адресов, как в реальных сетях). Таблицы большого размера сравнивать вручную весьма трудоёмко. От вас требуется написать программу для проверки эквивалентности двух заданных таблиц. \InputFile В первой строке \textit{\textbf{ }}входного файла записано целое число \textit{\textbf{N}} (от \textbf{1} до \textbf{100 000}) --- количество записей в первой таблице маршрутизации. Следующие \textit{\textbf{N}} строк содержат таблицу маршрутизации в описанном выше формате. Затем записано целое число \textit{\textbf{M}} (от \textbf{1} до \textbf{100 000}) --- количество записей во второй таблице. Следующие \textit{\textbf{M}} строк содержат вторую таблицу маршрутизации. \OutputFile В первой строке \textit{\textbf{ }}выходного файла выведите слово \textbf{YES} или \textbf{NO}.
Time limit 1 second
Memory limit 64 MiB
Input example #1
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
Output example #1
YES