Задачі
Маршрутизація
Маршрутизація
Для визначення маршрутів руху мережевих пакетів у сучасних мережах використовуються спеціальні пристрої --- маршрутизатори. У своїх діях маршрутизатор керується таблицею маршрутизації. Така таблиця являє набір рядків, які описують маршрути. Кожен рядок містить \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{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
У першому рядку вхідного файлу записано ціле число \textbf{N} (від \textbf{1} до \textbf{100 000}) --- кількість записів у першій таблиці маршрутизації. Наступні \textbf{N} рядків містять таблицю маршрутизації в описаному вище форматі. Потім записано ціле число \textbf{M} (від \textbf{1} до \textbf{100 000}) --- кількість записів у другій таблиці. Наступні \textbf{M} рядків містять другу таблицю маршрутизації.
\OutputFile
У першому рядку вихідного файлу виведіть слово \textbf{YES} або \textbf{NO}.
Вхідні дані #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
Вихідні дані #1
YES