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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:function.in   Ограничение памяти:64 Мб
Выходной файл:function.out  
Максимальный балл:100  

Условие

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

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

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

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

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

Пояснения к примерам

Система оценивания

Решения, правильно работающие только при N ≤ 20, будут оцениваться в 40 баллов.

Формат входного файла

Первая строка входного файла содержит одно натуральное число N

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

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 105

Примеры тестов

Входной файл (function.in) Выходной файл (function.out)
1
4
0110
1011
2
5
0100
11111
3
6
0000
No solution

0.113s 0.018s 13