eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Маршрутизація

Маршрутизація

Для визначення маршрутів руху мережевих пакетів у сучасних мережах використовуються спеціальні пристрої --- маршрутизатори. У своїх діях маршрутизатор керується таблицею маршрутизації. Така таблиця являє набір рядків, які описують маршрути. Кожен рядок містить \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 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #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