Задача №1883. Праздничная иллюминация
Для того, чтобы устроить праздничную иллюминацию по поводу проведения зимних сборов, у нас есть \(N\) разноцветных лампочек, занумерованных от \(1\) до \(N\). Лампочки управляются четырьмя кнопками.
Кнопка 1. При нажатии на эту кнопку все лампочки меняют состояние. Те, которые были включены, выключаются, а те, которые выключены — включаются.
Кнопка 2. При нажатии на эту кнопку меняют своё состояние лампочки с нечётными номерами.
Кнопка 3. При нажатии на эту кнопку меняют своё состояние лампочки с чётными номерами.
Кнопка 4. При нажатии на эту кнопку меняют своё состояние все лампочки c номерами \(3K+1\) (\(K\ge 0\)), т. е. \(1,4,7,\ldots\)
Есть счетчик \(C\), который записывает суммарное количество нажатий на кнопки. В начале праздника все лампочки включены, и счетчик \(C\) сброшен в 0. По значению счетчика \(C\) и конечному состоянию некоторых лампочек необходимо найти все возможные конечные конфигурации лампочек.
Первая строка входного файла содержит число \(N\) (\(1\le N\le 100\)). Во второй находится значение счетчика \(C\) (\(1\le C\le 10\,000\)). В третьей строке записаны номера лампочек, которые включены. Строка заканчивается числом \(-1\). В четвертой строке в таком же формате заданы лампочки, которые выключены.
В выходной файл выведите все возможные конечные состояния лампочек, по одному в строке. Каждая строка содержит \(N\) символов — 0, если соответствующая лампочка выключена, и 1 в противном случае. Конфигурации нужно выводить в лексикографическом порядке.
10 1 -1 7 -1
0000000000 0101010101 0110110110