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

Для визначення маршрутів для мережевих пакетів у сучасних мережах використовуються спеціальні пристрої, що називаються маршрутизаторами. Маршрутизатори працюють на основі таблиці маршрутів. Таблиця маршрутів складається з рядків, які описують маршрути, кожен рядок містить 3 поля: $D$, $M$ і $G$. Тут $D$ — IP-адреса мережі призначення, $M$ — маска, а $G$ — IP-адреса шлюзу (зауважимо, що в реальних таблицях полів може бути більше). Наприклад, рядок 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$-бітове число. Для зручності її записують у вигляді чотирьох десяткових чисел через крапку: кожен байт у десятковому вигляді, розділений крапками. Наприклад, 192.168.24.0 задає двійкове число 11000000101010000001100000000000. Те саме стосується і масок. Маски мають властивість, що їх бітове представлення містить лише одиниці, за якими йдуть лише нулі. Адреса шлюзу не може складатися виключно з нулів або одиниць.

Алгоритм вибору маршруту працює так. Припустимо, пакет адресовано за адресою $A$. Маршрутизатор переглядає всі записи й залишає тільки ті, для яких виконується умова D \land M = A \land M ($\wedge$ — це бітова операція "AND"). Серед них вибирається запис з найбільшою кількістю одиниць у масці — він і буде результатом. Гарантовано, що для будь-якої адреси є не більше одного такого запису.

Чим більша таблиця, тим повільніше працює маршрутизатор і більше ресурсів споживає. Але часто таку таблицю можна перетворити на еквівалентну з меншою кількістю рядків.

Наприклад, перша таблиця може виглядати так:

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

Друга таблиця може виглядати так:

192.168.0.0 255.255.252.0 192.168.14.1

192.168.2.0 255.255.254.0 192.168.14.2

Легко переконатися, що для будь-якої адреси призначення для обох таблиць результатом буде той самий шлюз (або жодного не буде визначено). Зверніть увагу, що в цій задачі адреса призначення може бути будь-яким $32$-бітовим числом (тобто немає спеціальних чи некоректних адрес, як у реальних мережах).

Порівнювати великі таблиці вручну — марудна справа. Ваше завдання — написати програму, яка перевірить еквівалентність двох заданих таблиць.