Оптимізація комбінаційних схем

Nathan O. Davis є студентом кафедри інтегрованих систем. Сьогодні він відвідує заняття з цифрових схем. Тема лекції — оптимізація комбінаційних схем. Комбінаційні схеми — це цифрові схеми, які реалізують булеву логіку за допомогою І-елементів та АБО-елементів. Зазвичай вони мають кілька входів і один вихід.

Наприкінці лекції він отримав домашнє завдання, як завжди. Завдання полягає в написанні програми, яка оптимізує комбінаційні схеми.

Специфікація оригінальної (неоптимізованої) схеми надається у вигляді таблиці істинності, наприклад, наступним чином:

Ця таблиця представляє схему з чотирма входами. Перший рядок означає, що коли вхід b дорівнює '0', а вхід d дорівнює '1', вихід має бути '1'. Вихід 'x' означає "не має значення", тобто неважливо, чи вихід для відповідного шаблону буде '0' чи '1'. Загалом, ця таблиця представляє схему, яка видає '1' для входів, що задовольняють (¬b ∧ d) ∨ (a ∧ c ∧ ¬d), або '0' чи '1' для входів, що задовольняють (¬b ∧ c) ∨ (¬a ∧ b) ∨ (a ∧ d), і '0' для будь-яких інших вхідних шаблонів.

Як виглядають оптимізовані версії цієї схеми? Ось приклад:

Схема, що імпліцитно представлена цією таблицею істинності, видає '1' для входів, що задовольняють (c∨d), і '0' для всіх інших шаблонів. Ви повинні зауважити, що ця схема відповідає специфікації оригінальної схеми.

Ви можете побачити, що розмір схеми зменшився в порівнянні з оригінальною. Насправді, наведена вище схема є найбільш оптимізованою серед усіх схем, що відповідають оригінальній специфікації. Тут ми кажемо, що схема є більш оптимізованою, ніж інша, коли вона має меншу кількість рядків у таблиці. Коли дві схеми мають однакову кількість рядків, та, що має меншу кількість 0/1 у таблиці, вважається більш оптимізованою.

Тепер, будь ласка, напишіть програму, що здійснює цю оптимізацію, щоб допомогти Нейтану!

Вхідні дані

Вхід складається з кількох тестових випадків.

Перша строка кожного тестового випадку складається з двох цілих чисел N та M. Ціле число N (1 ≤ N ≤ 6) - це кількість вхідних сигналів, а M (1 ≤ M ≤ 2^N) - це кількість рядків таблиці.

Потім слідують M рядків, що описують вхідну схему. Кожен рядок складається з рядка S довжиною N та символу C. Рядок S представляє вхідний шаблон. Кожен символ рядка S може бути '0', '1' або '-'. Символ C може бути '1' або 'x', що означає, що бажаний вихід для вхідного шаблону S - це '1' або "не має значення" відповідно. Ви можете припустити, що вхід містить принаймні один рядок з C, що дорівнює '1'.

Кінець вводу позначається рядком "0 0".

Вихідні дані

Виведіть таблицю, що позначає найбільш оптимізовану схему для кожного тестового випадку. Для кожного рядка таблиці, що представляє вихідну схему, ви повинні вивести рядок, що відповідає вхідному шаблону, в окремому рядку. Вам не потрібно писати специфікацію виходу '1' або 'x', оскільки найбільш оптимізована схема не має шаблонів з неоднозначними виходами.

Коли є кілька можливих рішень, виведіть будь-яке з них. Також ви можете виводити рядки таблиці в довільному порядку.

Кожен вивід має бути перед рядком, що позначає номер тестового випадку. Виводи з різних тестових випадків мають бути відокремлені одним порожнім рядком.