Задача №933. Контроль доступа
Вася разрабатывает новый веб-сервер. В настоящее время он работает над функцией, осебспечивающей поддержку списков контроля доступа. Список контроля доступа позволяет ограничить доступ к некоторым ресурсам веб-сайта, основываяь на основании IP-адреса запрашивающей стороны.
Каждый IP-адрес \(-\) это 4-байтный номер, который записан байт за байтом в десятичной записи. Байты разделены точками следующим образом: <<byte0.byte1.byte2.byte3>> (кавычки добавлены для ясности). Каждый байт записывается как десятичное число от 0 до 255 (включительно) без ведущих нулей. IP-адреса организованы в IP-сети. IP сети описывается двумя 4-байтовыми числами - сетевым адресом и маской сети. И сетевой адрес и маска сети записаны в той же форме, что и IP-адреса. Для того чтобы понять смысл сетевого адреса и маски сети рассмотрим их двоичное представление. Двоичное представление IP адреса, сетевого адреса и маски сети состоит из 32 бит: 8 бит для byte0 (от старших к младшим), затем по 8 бит для byte1, 8 бит для byte2 и 8 бит для byte3.
IP сеть содержит \(2N\) IP-адресов, где \(0 \leq N \leq 32\). В маске сети первые 32–N бита установлены в единицы, и последние \(N\) бит установлены в ноль. Сетевой адрес имеет произвольные \(32–N\) первых бит, а последние \(N\) бит установлен в ноль. IP сеть содержит все IP-адреса, первые \(32-N\) бит которых равны \(32–N\) первых бит сетевого адреса с произвольными \(N\) последними битами. Например, IP сеть с сетевым адресом 194.85.160.176 и сетевая маска 255.255.255.248 содержит 8 IP-адресов, с 194.85.160.176 по 194.85.160.183 (включительно).
IP сети, как правило, обозначается как <<byte0.byte1.byte2.byte3/S>>, где <<byte0.byte1.byte2.byte3>> \(-\) сетевой адрес, \(S\) \(-\) это число бит, установленных в единицу в маске сети. Например, IP сети из предыдущего абзаца обозначается как 194.85.160.176/29. Список контроля доступа содержит упорядоченный список правил. Каждое правило имеет одну из следующих форм:
deny from <IP network> \(-\) запрещает доступ к ресурсу для любого IP из заданной сети.
deny from <IP address> \(-\) запрещает доступ к ресурсу для указанного IP-адреса.
allow from <IP network> \(-\) разрешает доступ к ресурсу для любого IP из заданной сети.
allow from <IP address> \(-\) разрешает доступ к ресурсу для указанного IP-адреса.
Когда кто-нибудь обращается к какому-либо ресурсу, первым делом проверяется IP-адрес обращающегося по списку контроля доступа. Правила проверяются в том порядке, в котором они перечислены, и применяется первое выполняющееся правило. Если ни одно из правил не соответствует IP-адресу запрашивающей стороны, то доступ предоставляется.
По известному списку контроля доступа и списку запросов от IP-адресов, необходимо выяснить для каждого из запросов будет ли предоставлен доступ к ресурсу.
Первая строка ввода содержит число \(N\) \(-\) количество правил в списке контроля доступа (\(0 \leq N \leq 100 000\)). Следующие \(N\) строк содержат правила по одному в строке. IP сеть всегда записывается как <<byte0.byte1.byte2.byte3/S>>. Следующая строка содержит число \(M\) \(-\) количество IP адресов, которые следует проверить (\(0 \leq M \leq 100 000\)). Следующие \(M\) строк содержат по одному IP адресу в строке.
Для каждого из \(M\) IP-адресов выведите <<A>>, если доступ будет предоставлен, и <<D>> иначе. Все символы следует выводить слитно, не разделяя пробелами.
4 allow from 10.0.0.1 deny from 10.0.0.0/8 allow from 192.168.0.0/16 deny from 192.168.0.1 5 10.0.0.1 10.0.0.2 194.85.160.133 192.168.0.1 192.168.0.2
ADAAA