eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Совпадение длиннейшего префикса

Совпадение длиннейшего префикса

Лимит времени 2 секунды
Лимит использования памяти 122 MiB

В интернете маршрутизатор пересылает пакеты по их адресу назначения, используя таблицу пересылки. Эта таблица для каждого пункта назначения определяет путь (если таковой имеется), по которому должен отправиться пакет. Адресом назначения является 32-битовое беззнаковое целое. В таблице переадресации содержится много различных префиксов (тысячи), каждый префикс представляется кортежем (m, l), где m - маска адреса (беззнаковое целое), а l - длина, указывающая на количество существенных бит в маске. Адресу назначения d соответствует префикс (m, l), если l старших бит d совпадают с l старшими битами m.

Совпадение длиннейшего префикса: когда поступает пакет данных, маршрутизатор должен найти в своей базе самый длинный префикс, совпадающий с адресом назначения пакета. Вам следует реализовать Совпадение Наидлиннейшего Префикса для маршрутизатора, который обрабатывает несколько миллионов пакетов.

Входные данные

Первая строка содержит два целых числа x (x10000) и y. x указывает на количество префиксов в таблице пересылки маршрутизатора, а y задает количество передаваемых пакетов. Следующие x строк описывают префиксы: каждая строка задает один префикс шестнадцатеричной маской (содержащий не более 32 бит), за которым следует его длина len (0 < len32) по основанию 10. Каждый префикс идентифицируется числом, равным номером строки в которой он появляется минус один (то есть первый префикс имеет id 0, второй 1, и так далее). Следующие y строк задают адреса назначения, куда пакеты должны быть доставлены, по одному пакету в каждой строке (адреса также задаются в шестнадцатеричном формате).

Выходные данные

Вывести y строк. Строка k содержит исход сравнения самого длинного префикса для k-го входного адреса. Результатом является либо идентификатор наидлиннейшего совпадающего префикса, либо -1 если совпадение не найдено.

Пример

Входные данные #1
5 5
FFFFFF00 24
FF000000 8
AF230000 16
3 31
0 0
FFFF0000
F0FF0000
FFFFFF00
AF320000
2
Выходные данные #1
1
4
0
4
3
Источник 2012 Southeastern Europe Regional Contest, Бухарест, Винница, Октябрь 13, Задача D