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

Условие

Ник разрабатывает новый веб-сервер. В данный момент он работает над поддержкой списков контроля доступа. Список контроля доступа позволяет запретить доступ к некоторым ресурсам на веб сайте на основании 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

Задача B. Доска объявлений ≡

Условие

На входе в университет висит огромная прямоугольная доска объявлений размером h × w (h — высота, а w — ширина). Доска — это место, где вывешиваются всевозможные объявления о ближайших контестах, изменениях в меню столовой и другая важная информация.

Первого сентября доска была пустой. Один за одним добавлялись объявления.

Каждое объявление — это полоска бумаги единичной высоты. Более точно, i-ое объявление — это прямоугольник размером 1 × w_i.

Когда кто-либо добавляет новое объявление на доску, он всегда выбирает самую высокую возможную позицию для объявления. Среди всех возможных самых высоких позиций он выбирает самую левую.

Если для нового объявления нет места, оно не помещается на доску.

Даны размеры доски и объявлений, ваша задача — найти номера рядов, в которые будут помещены объявления.

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

Первая строка входного файла содержит три целых числа h, w, и n — размеры доски и количество объявлений.

Каждая из следующих n строк содержит целое число w_i — ширину i-ого объявления.

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

Для каждого объявления (в порядке, данном во входном файле) выведите одно число — номер ряда, в который помещается объявление. Ряды занумерованы от 1 до h, начиная с верхнего ряда. Если объявление не может быть помещено на доску, выведите "-1" для этого объявления.

Ограничения

1 ≤ h, w ≤ 10⁹, 1 ≤ n ≤ 200000, 1 ≤ w_i ≤ 10⁹.

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

3 5 5
2
4
3
3
3

1
2
1
3
-1

Задача C. Класс ≡

Условие

Доктор Странный действительно странный. На каждой лекции он вычисляет заполненность класса и если она маленькая, уменьшает все оценки в семестре на 1. Поэтому студенты хотят максимизировать заполненность класса.

Заполненность класса — это минимум из заполненности рядов и заполненности колонок. Заполненность колонок — это максимальное количество студентов в одной колонке, а заполненность рядов  — максимальное количество студентов в ряду.

Например, есть 16 студентов, изображенных на картинке слева (занятые парты темные). Заполненность рядов этого расположения составляет 5 ( в четвертом ряду), а заполненность колонок 3 (1, 3, 5, 6 колонки). Итак, заполненность класса равна 3. Но если студенты пересядут как показано на картинке справа, то заполненность колонок станет равна 4 (5-ая колонка), и тогда заполненность класса также станет равна 4.

Студентам Доктора Странного необходимо знать расположение, которое максимизирует заполненность класса, поэтому они просят вас написать программу которая ее вычислит.

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

В первой строке входного файла содержатся три числа: n, r и c — количество студентов, рядов и колонок в классе.

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

В первой строке выходного файла должно содержаться одно число — максимальная возможная заполненность класса.

Следующие r строк должны содержать оптимальное расположение студентов. Каждая строка должна содержать описание одного ряда. Описание ряда — это строка из c символов, либо ".", либо "#", где "." означает пустую парту, а "#" — заполненную. Если допустимо несколько оптимальных расположений, выведите любое.

Ограничения

1 ≤ r, c ≤ 100, 1 ≤ n ≤ r × c.

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

16 4 6

4
.####.
#..###
#...##
###.##

Задача D. Счета ≡

Условие

Финансовый кризис заставил многие центральные банки хранить большое количество наличных денег на счетах, чтобы обеспечить ликвидность и сохранить кредитные рынки.

Центральный банк Флатландии планирует вывести на рынок n депозитов. Каждый депозит характеризуется своим количеством a_i.

Правила Фладладского рынка требуют, чтобы каждый депозит рефинансировался на одинаковое целое число каждый день. Это означает, что депозит объема a и запрос длины b подходят друг другу если и только если a делится на b.

Дана информация о депозитах и запросах, найдите количество пар депозит-запрос, которые подходят друг другу.

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

Первая строка входного файла содержит n — количество депозитов. Вторая строка входного файла содержит n целых чисел: a₁, a₂, …, a_n.

Третья строка содержит m — количество запросов. Четвертая строка содержит m целых числе: b₁, b₂, …, b_m.

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

Выведите одно число - количество подходящих пар.

Для приведенного примера подходят следующие пары: (3, 1) дважды (как (a₁, b₁) и как (a₁, b₂)), (3, 3), (4, 1) дважды, (4, 2), (5, 1) дважды, (6, 1) дважды, (6, 2), и (6, 3).

Ограничения

1 ≤ n ≤ 100000, 1 ≤ a_i ≤ 10⁶,

1 ≤ m ≤ 100000, 1 ≤ b_i ≤ 10⁶.

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

4
3 4 5 6
4
1 1 2 3

12

Задача E. Заколдованное зекрало ≡

Условие

Алиса любит две вещи — свое зеркало и свои кубики. Кубики Алисы сделаны чтобы помочь детям выучить алфавит, поэтому на их верхних гранях написаны буквы. Алиса любит играть с кубиками рядом с зеркалом.

Когда Алиса выучила алфавит, она заметила, что что-то не так с ее зеркалом! Буква на кубике в отражении может оказаться другой. Алисе очень понравился этот эффект, и она придумала новую игру, пытаясь составить разные слова из кубиков в настоящем мире и в зазеркалье одновременно.

Правила этой игры следующие. Алиса создает линию из нескольких кубиков, которая образует слово S₁. Эта линия показывается в зеркале в виде некоторого слова S₂, которое может отличаться от отражения S₁ из-за заколдованности зеркала. Но длина каждого из этих слов одинакова и равна N.

Алиса может повторять следующий шаг. Она выбирает два произвольных кубика i и j, и меняет их местами. Отраженная в зеркале Алиса делает то же самое с отраженной линией, за исключением того, что она, конечно, меняет местами кубики с позициями N − i + 1 и N − j + 1.

Цель - создать слово T₁ в настоящем мире и одновременно слово T₂ в зазеркалье. Алисе интересно, возможно ли это и она просит вашей помощи. Напишите программу, которая поможет определить, может ли быть достигнута цель.

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

Входной файл содержит четыре слова S₁, S₂, T₁ и T₂, в указанном прядке, каждое на отдельной строке. Все слова имеют одинаковую длину N и состоят только из заглавных английских букв.

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

Если цель может быть достигнута, выведите "Yes". Иначе выведите "No".

Ограничения

1 ≤ N ≤ 100.

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

TEAM
TIED
MATE
EDIT

Yes

TEAM
MATE
TAME
MEAT

No

AAAA
AAAA
AAAA
AAAA

Yes