|
При отправке сетевых пакетов маршрутизаторами в IP-сетях для определения адреса следующего узла применяются таблицы маршрутизации. Упрощенно каждая строка такой таблицы содержит 4 поля:
* D - IP-адрес сети назначения,
* M - Маска сети назначения,
* G - IP-адрес шлюза
* C - метрика (стоимость маршрута)
Поля D,M,G - 32-битные целые числа, но для удобства восприятия они представляются в десятично-точечной нотации: поле разбивается на 4 байта, они записываются в десятичном виде и отделяются друг от друга точками. Например, адресу 11000000101010000000000000000001 соответствует запись 192.168.0.1. Особенность поля маски состоит в том, что в битовом представлении маски вначале идут только единицы, затем - только нули. Метрика - целое число в диапазоне от 0 до 1000, меньшее значение имеет более высокий приоритет.
Когда маршрутизатору нужно переслать очередной пакет на адрес назначения A, выполнятся следующие действия:
1. Берутся только те записи , для которых выполняется условие:
(D and M) = (A and M), где and - побитовая операция И.
2. Из этих записей оставляются только те, где количество единичных битов в маске максимально.
3. Берётся запись с наименьшим значением метрики (если таких записей несколько, то берётся первая из них в том порядке, в каком записи шли во входном файле).
Дана таблица маршрутизации и адреса назначения отправляемых пакетов. Требуется для каждого пакета вывести адрес шлюза, на который его следует отправить. Если ни одной подходящей записи нет, следует вывести сообщение "NO ROUTE".
Формат входного файла:
Первая строка входного файла содержит целое число N (1<=N<=1000) - количество записей в таблице. Каждая из следующих N строчек содержит очередную запись в таблице маршрутизации - поля D, M, G и C, разделённые пробелом. В следующей строчке записано число P (1<=P<=10000) - количество пакетов, которые нужно отправить. В каждой из следующих P строчек стоит адрес назначения соответствующего пакета.
Формат выходного файла:
Для каждого пакета по порядку выведите адрес шлюза, на который его нужно отправить, или сообщение "NO ROUTE", если нет ни одного подходящего маршрута
Примеры:
| STDIN | STDOUT |
3
192.168.0.0 255.255.255.0 192.168.5.1 0
192.168.0.32 255.255.255.224 192.168.7.1 20
192.168.0.32 255.255.255.224 192.168.6.1 10
3
192.168.0.96
192.168.0.57
192.168.8.1
|
192.168.5.1
192.168.6.1
NO ROUTE
|
|
