Будем называть рекуррентной двоичной последовательностью бесконечную последовательность (a0, a1, ...) из нулей и единиц, задающуюся соотношением:
an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2), где
— заранее фиксированные коэффициенты и
n ≥ k. Будем считать, что не все
ci нули.
Заметим, что такая последовательность однозначно восстанавливается из любого своего k-кортежа {as, as + 1, ..., as + k - 1}, поэтому в частности она является периодической. Более того, если в кортеже содержатся только нули, тогда и сама последовательность состоит лишь из нулей, что не очень-то интересно. В противном случае, период последовательности не превосходит 2k - 1, так как любой k-кортеж однозначно определяет следующий элемент, и существует всего 2k - 1 ненулевых k-кортежей. Будем называть последовательность длинной, если ее минимальный период в точности равен 2k - 1. Вам требуется по данному k предъявить длинную последовательность или определить, что ее не существует.
Выходные данные
Если для данного k не существует длинной последовательности, выведите одно число «-1» (без кавычек). Иначе первая строка вывода должна содержать коэффициенты: c1, c2, ..., ck. Вторая строка должна содержать первые k элементов последовательности: a0, a1, ..., ak - 1. Все числа (элементы и коэффициенты) должны быть 0 или 1, причем хотя бы один коэффициент должен быть 1.
Если решений несколько, выведите любое.
Примечание
1. В первом случае: c1 = 1, c2 = 1, поэтому an = an - 1 + an - 2 (mod 2). Получается последовательность:
с периодом 3 = 22 - 1.
2. В втором случае: c1 = 0, c2 = 1, c3 = 1, поэтому an = an - 2 + an - 3 (mod 2). Последовательность имеет вид:
ее период равен 7 = 23 - 1.
Периоды окрашены в разные цвета.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
1 1
1 0
|
|
2
|
3
|
0 1 1
1 1 1
|