Совпадение длиннейшего префикса
В интернете маршрутизатор пересылает пакеты по их адресу назначения, используя таблицу пересылки. Эта таблица для каждого пункта назначения определяет путь (если таковой имеется), по которому должен отправиться пакет. Адресом назначения является 32-битовое беззнаковое целое. В таблице переадресации содержится много различных префиксов (тысячи), каждый префикс представляется кортежем (m, l), где m - маска адреса (беззнаковое целое), а l - длина, указывающая на количество существенных бит в маске. Адресу назначения d соответствует префикс (m, l), если l старших бит d совпадают с l старшими битами m.
Совпадение длиннейшего префикса: когда поступает пакет данных, маршрутизатор должен найти в своей базе самый длинный префикс, совпадающий с адресом назначения пакета. Вам следует реализовать Совпадение Наидлиннейшего Префикса для маршрутизатора, который обрабатывает несколько миллионов пакетов.
Входные данные
Первая строка содержит два целых числа x (x ≤ 10000) и y. x указывает на количество префиксов в таблице пересылки маршрутизатора, а y задает количество передаваемых пакетов. Следующие x строк описывают префиксы: каждая строка задает один префикс шестнадцатеричной маской (содержащий не более 32 бит), за которым следует его длина len (0 < len ≤ 32) по основанию 10. Каждый префикс идентифицируется числом, равным номером строки в которой он появляется минус один (то есть первый префикс имеет id 0, второй 1, и так далее). Следующие y строк задают адреса назначения, куда пакеты должны быть доставлены, по одному пакету в каждой строке (адреса также задаются в шестнадцатеричном формате).
Выходные данные
Вывести y строк. Строка k содержит исход сравнения самого длинного префикса для k-го входного адреса. Результатом является либо идентификатор наидлиннейшего совпадающего префикса, либо -1 если совпадение не найдено.