Збіг найдовшого префікса#3844
В інтернеті маршрутизатор пересилає пакети на основі їхньої адреси призначення, використовуючи таблицю маршрутизації. Ця таблиця визначає шлях для кожної адреси призначення (якщо такий існує), яким має бути відправлений пакет. Адреса призначення — це -бітове беззнакове ціле число. У таблиці маршрутизації міститься багато різних префіксів (тисячі), кожен з яких представлений кортежем (, ), де — це маска адреси (беззнакове ціле число), а — довжина, що вказує на кількість значущих бітів у масці. Адреса призначення відповідає префіксу (, ), якщо старших бітів збігаються з старшими бітами .
Збіг найдовшого префікса: коли надходить пакет даних, маршрутизатор повинен знайти у своїй базі найдовший префікс, що збігається з адресою призначення пакета. Вам потрібно реалізувати алгоритм для визначення найдовшого префікса, що збігається, для маршрутизатора, який обробляє кілька мільйонів пакетів.
Перший рядок містить два цілі числа (x \le 10000) і . вказує на кількість префіксів у таблиці маршрутизації, а — на кількість пакетів, що передаються. Наступні рядків описують префікси: кожен рядок задає один префікс у вигляді шістнадцяткової маски (що містить не більше біт), за якою слідує її довжина (0 < len \le 32) у десятковій системі. Кожен префікс ідентифікується числом, що дорівнює номеру рядка, в якому він з'являється, мінус один (тобто перший префікс має id = 0, другий — , і так далі). Наступні рядків задають адреси призначення, куди пакети повинні бути доставлені, по одному пакету в кожному рядку (адреси також задаються у шістнадцятковому форматі).
Виведіть рядків. Рядок містить результат порівняння найдовшого префікса для -ої вхідної адреси. Результатом є або ідентифікатор найдовшого префікса, що збігається, або , якщо збіг не знайдено.
Приклад 1