E. Длинная последовательность
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Будем называть рекуррентной двоичной последовательностью бесконечную последовательность (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 (2 ≤ k ≤ 50).

Выходные данные

Если для данного k не существует длинной последовательности, выведите одно число «-1» (без кавычек). Иначе первая строка вывода должна содержать коэффициенты: c1, c2, ..., ck. Вторая строка должна содержать первые k элементов последовательности: a0, a1, ..., ak - 1. Все числа (элементы и коэффициенты) должны быть 0 или 1, причем хотя бы один коэффициент должен быть 1.

Если решений несколько, выведите любое.

Примеры
Входные данные
2
Выходные данные
1 1
1 0
Входные данные
3
Выходные данные
0 1 1
1 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.

Периоды окрашены в разные цвета.