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

Натан О. Дэвис — студент кафедры интегрированных систем. Сегодня он посещает лекцию по цифровым схемам, посвящённую оптимизации комбинаторных схем. Комбинаторные схемы — это цифровые устройства, реализующие булеву логику с помощью И- и ИЛИ-элементов. Обычно они имеют несколько входов и один выход.

Как обычно, в конце лекции он получил домашнее задание. Задача заключается в написании программы для оптимизации комбинаторных схем.

Спецификация исходной (неоптимизированной) схемы представлена в виде таблицы истинности, например, так:

Эта таблица описывает схему с четырьмя входами. Первая строка указывает, что когда вход 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', так как наиболее оптимизированная схема не имеет шаблонов с неоднозначными выходами.

Когда существует несколько возможных решений, выведите любое из них. Также вы можете выводить строки в таблице в произвольном порядке.

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