Захист цифрового контенту
Ден працює в компанії з захисту цифрового контенту, яка відповідає за захист контенту на 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, які задовольняють вищезазначеним вимогам і мають мінімальну кардинальність, у зростаючому порядку, розділені пробілами.