CF86E.Long sequence

A sequence _a_0, _a_1, ... is called a recurrent binary sequence, if each term a__i (i = 0, 1, ...) is equal to 0 or 1 and there exist coefficients such that

a__n = _c_1·a__n - 1 + _c_2·a__n - 2 + ... + c__k·a__n - k (mod 2),

for all n ≥ k. Assume that not all of c__i are zeros.

Note that such a sequence can be uniquely recovered from any k-tuple {a__s, a__s + 1, ..., a__s + k - 1} and so it is periodic. Moreover, if a k-tuple contains only zeros, then the sequence contains only zeros, so this case is not very interesting. Otherwise the minimal period of the sequence is not greater than 2_k_ - 1, as k-tuple determines next element, and there are 2_k_ - 1 non-zero k-tuples. Let us call a sequence long if its minimal period is exactly 2_k_ - 1. Your task is to find a long sequence for a given k, if there is any.

一个序列 $a_0, a_1, \dots$ 称为递归二进制序列，如果每一项 $a_i$（其中 $i = 0, 1, \dots$）均取值为 $0$ 或 $1$，且存在系数

使得对所有 $n \ge k$，均有

$$a_n = c_1 \cdot a_{n-1} + c_2 \cdot a_{n-2} + \dots + c_k \cdot a_{n-k} \pmod{2},$$

其中并非所有 $c_i$ 均为零。

注意：该序列可由任意一个 $k$ 元组 $\{a_s, a_{s+1}, \dots, a_{s+k-1}\}$ 唯一确定，因此该序列必为周期序列。此外，若某 $k$ 元组全为零，则整个序列恒为零，此情形无甚趣味。否则，该序列的最小周期至多为 $2^k - 1$，因为每个 $k$ 元组唯一决定下一个元素，而共有 $2^k - 1$ 个非零的 $k$ 元组。我们称一个序列是长序列，当且仅当其最小周期恰好等于 $2^k - 1$。你的任务是：对给定的 $k$，若存在长序列，则找出一个。

Input contains a single integer k (2 ≤ k ≤ 50).

输入包含一个整数 $k$（$2 \leq k \leq 50$）。

If there is no long sequence for a given k, output "-1" (without quotes). Otherwise the first line of the output should contain k integer numbers: _c_1, _c_2, ..., c__k (coefficients). The second line should contain first k elements of the sequence: _a_0, _a_1, ..., a__k - 1. All of them (elements and coefficients) should be equal to 0 or 1, and at least one c__i has to be equal to 1.

If there are several solutions, output any.

如果对于给定的 $k$ 不存在长序列，则输出 -1（不带引号）。否则，输出的第一行应包含 $k$ 个整数：$c_1,\,c_2,\,...,\,c_k$（系数）；第二行应包含该序列的前 $k$ 个元素：$a_0,\,a_1,\,...,\,a_{k-1}$。所有这些数（包括序列元素和系数）都必须为 $0$ 或 $1$，且至少有一个 $c_i$ 等于 $1$。

若存在多个解，输出任意一个即可。

1. In the first sample: _c_1 = 1, _c_2 = 1, so a__n = a__n - 1 + a__n - 2 (mod 2). Thus the sequence will be:

so its period equals 3 = 22 - 1.

2. In the second sample: _c_1 = 0, _c_2 = 1, _c_3 = 1, so a__n = a__n - 2 + a__n - 3 (mod 2). Thus our sequence is:

and its period equals 7 = 23 - 1.

Periods are colored.

1. 在第一个样例中：$c_1 = 1$，$c_2 = 1$，因此 $a_n = a_{n-1} + a_{n-2} \pmod{2}$。于是该序列为：

其周期为 $3 = 2^2 - 1$。

2. 在第二个样例中：$c_1 = 0$，$c_2 = 1$，$c_3 = 1$，因此 $a_n = a_{n-2} + a_{n-3} \pmod{2}$。于是该序列为：

其周期为 $7 = 2^3 - 1$。

周期部分已用颜色标出。