Задача G. Списки контроля доступа ≡

Условие

Ник разрабатывает новый веб-сервер. В данный момент он работает над поддержкой списков контроля доступа. Список контроля доступа позволяет запретить доступ к некоторым ресурсам на веб сайте на основании IP адреса пользователя.

Каждый IP адрес представляет собой четырехбайтовое число, записанное байт за байтом в десятичных числах, разделенных точками "byte0.byte1.byte2.byte3". Каждый байт записан как десятичное число от 0 до 255 (включительно) без лидирующих нулей. IP адреса собраны в IP сети.

IP сеть описывается двумя четерехбайтовыми числами — адресом сети и маской сети. Оба записываются в той же нотации, что и IP адрес.

Чтобы понять значение адреса сети и маски сети рассмотрим их двоичное представление. Двоичное представление всех адресов состоит из 32 бит: 8 бит для byte0, далее 8 бит для byte1, далее 8 бит для byte2, и затем 8 бит для byte3.

IP сеть содежрит набор из 2ⁿ IP адресов, где 0 ≤ n ≤ 32. В маске сети всегда первые 32 − n бит установлены в 1, а n последних бит установлены в 0 в двоичном представлении. Адрес сети имеет произвольные первые 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 — количество бит установленных в 1 в маске сети. Например, IP сеть из предыдущего абзаца записывается как 194.85.160.176/29.

Список котроля доступа содержит упорядоченный список правил. Каждое правило записано в одной из следующих форм:

• "deny from " — запрещает доступ к ресурсу любому IP из указанной IP сети.
• "deny from " — запрещает доступ к ресурсу указанному IP адресу.
• "allow from " — разрешает доступ к ресурсу любому IP из указанной IP сети.
• "allow from " — разрешает доступ к ресурсу указанному IP адресу.

Когда клиент запрашивает некоторый ресурс, его IP адрес сначала проверяется по списку контроля доступа. Правила просматриваются в порядке их перечисления и применяется первое подходящее. Если не подходит ни одно из правил, доступ разрешается.

Дан список котроля доступа и списовк запрашивающих IP адресов, найдите для каждого запроса, будет ли разрешен доступ к ресурсу.

Формат входного файла

В первой строке входого файла содержится n — количество правил в списке контроля доступа. Следующие n строк содержат правила по одному в строке. IP сеть всегда обозначается как "byte0.byte1.byte2.byte3/s".

Следующая строка содержит m — количество IP адресов для проверки. Следующие m строк содержат IP адреса для проверки по одному в строке.

Формат выходного файла

Для каждого запроса выведите 'A' если доступ к ресурсу будет открыт, либо 'D' в противном случае. Выведите все ответы в одной строке, НЕ разделяйте их пробельными символами.

Ограничения

0 ≤ n ≤ 100000, 1 ≤ m ≤ 100000.

Примеры тестов

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