序列 a0, a1, ... 称为循环二元序列,如果每个项 ai (i = 0, 1, ...) 等于 0 或 1 并且存在系数 $$c_1, c_2, \ldots, c_k \in \{0, 1\}$$ 使得
an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2),
请注意,这样的序列可以从任何 k 元组 {as, as + 1, ..., as + k - 1} 中唯一恢复,因此它是周期性的。此外,如果 k 元组仅包含零,则序列也仅包含零,因此这种情况不是很有趣。否则序列的最小周期不大于2k - 1,因为k元组决定下一个元素,并且有2k - 1个非零k元组。如果一个序列的最小周期正好是 2k - 1,我们称该序列为长序列。您的任务是针对给定 k(如果存在)找到一个长序列。
输入
输入包含单个整数 k (2 ≤ k ≤ 50)。
输出
如果给定的 k 没有长序列,则输出“-1”(不带引号)。否则,输出的第一行应包含 k 个整数:c1、c2、...、ck(系数)。第二行应包含序列的前 k 个元素:a0, a1, ..., ak - 1。所有这些(元素和系数)应等于 0 或 1,并且至少有一个 ci 必须等于 1。
如果有多个解,则输出任意一个。
示例
输入 #1
2
输出 #1
1 1 1 0
输入 #2
3
输出 #2
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。
句点是彩色的。