Задача Булева функция

Описание

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция f сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции f .

Если задана булева функция f и набор из N булевых значений , то результат цепного вычисления этой булевой функции определяется следующим образом:

• если N = 1, то он равен a ₁ ;
• если N > 1, то он равен результату цепного вычисления булевой функции f для набора из (N-1) булевого значения , который получается путем замены первых двух булевых значений в наборе из N булевых значений на единственное булево значение – результат вычисления функции f от a ₁ и a ₂ .

Например, если изначально задано три булевых значения: a ₁ = 0, a ₂ = 1, a ₃ = 0, а функция f - ИЛИ (OR), то после первого шага получается два булевых значения - (0 OR 1) и 0, то есть, 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию f и попросила одного из учеников выбрать такие N булевых значений a _i , чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно большим.

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

Формат входных данных

Первая строка входного файла содержит одно натуральное число N (2 <= N <= 100000).

Вторая строка входного файла содержит описание булевой функции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат вычисления функции в случае, если оба аргумента – нули, второе – результат в случае, если первый аргумент – ноль, второй – единица, третье – результат в случае, если первый аргумент – единица, второй – ноль, а четвертый – в случае, если оба аргумента – единицы.

Формат выходных данных

В выходной файл необходимо вывести строку из N символов, определяющих искомый набор булевых значений a _i с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу "No solution".