Защита цифрового контента
Дэн работает в компании, занимающейся защитой цифрового контента, которая отвечает за защиту данных на blu-ray дисках с использованием стандарта, известного как Anti Content Misuse (ACM).
Стандарт ACM функционирует следующим образом. Предположим, что у нас есть 2^n blu-ray приводов или плееров. Эти 2^n приводы представляются в виде листьев полного бинарного дерева высоты n, так что каждый путь от корня до листа состоит из n ребер. Каждому узлу u в этом бинарном дереве присваивается идентификационный номер и случайный ключ k_u. Номера присваиваются следующим образом: корню r присваивается номер 1. Левый и правый потомки внутреннего узла с номером i получают номера 2i и 2i+1 соответственно. Эта схема обеспечивает уникальность номеров для каждого узла в дереве. Ключи, находящиеся в узлах, недоступны пользователям blu-ray, но доступны производителям blu-ray приводов. Каждому blu-ray плееру присваивается идентификационный номер i (2^n ≤ i ≤ 2^{n+1}−1) его соответствующего листа в дереве. Производитель blu-ray приводов встраивает ключи, связанные с узлами на пути от корня до листа с номером i, в плеер с номером i.
Для шифрования контента blu-ray диска компания создает случайный ключ k, называемый мастер-ключом. Сначала они шифруют k с использованием ключа k_r (напомним, r — это корневой узел бинарного дерева) и записывают его на диск в качестве заголовка. Затем они шифруют контент с помощью k и записывают зашифрованные данные на blu-ray диск. Blu-ray привод сначала расшифровывает заголовок с использованием ключа k_r, встроенного в него, и восстанавливает мастер-ключ k, а затем расшифровывает контент с использованием ключа k.
К сожалению, ключи, встроенные в набор blu-ray приводов R, были раскрыты хакерами и опубликованы в интернете. В результате мы не можем зашифровать мастер-ключ k с использованием любого из этих раскрытых ключей. Например, поскольку все blu-ray приводы содержат k_r, вышеописанная схема шифрования больше не работает. В стандарте ACM предусмотрено решение для этой ситуации. За счет увеличения заголовка индустрия может безопасно зашифровать контент нового blu-ray диска. Они тщательно выбирают подмножество нераскрытых ключей K в бинарном дереве так, чтобы все blu-ray приводы, кроме приводов в R, имели хотя бы один из ключей в K. Они шифруют мастер-ключ k с каждым ключом k' из K и помещают результат в заголовок (т.е. в заголовке |K| шифротекстов). Теперь каждый активный blu-ray привод может расшифровать хотя бы один из шифротекстов в заголовке и восстановить мастер-ключ k. Дэну нужна ваша помощь, чтобы определить подмножество ключей K с минимальной мощностью (что приводит к наименьшему заголовку), учитывая идентификаторы взломанных приводов.
Входные данные
Входные данные состоят из одного теста. Тест состоит из двух строк. Первая строка содержит два целых числа n и |R|, где 1 ≤ n ≤ 62 и 1 ≤ |R| ≤ 1000. |R| — это мощность множества R, набора раскрытых приводов. Вторая строка содержит |R| целых чисел, которые являются идентификаторами раскрытых blu-ray приводов. Вы можете предположить, что существует хотя бы один не взломанный blu-ray привод.
Выходные данные
Выведите идентификаторы узлов, соответствующих ключам в K, удовлетворяющим вышеуказанным требованиям и имеющим минимальную мощность, в порядке возрастания и разделенных пробелами.