CF901B.GCD of Polynomials

Suppose you have two polynomials and . Then polynomial can be uniquely represented in the following way:

This can be done using long division. Here, denotes the degree of polynomial P(x). is called the remainder of division of polynomial by polynomial , it is also denoted as .

Since there is a way to divide polynomials with remainder, we can define Euclid's algorithm of finding the greatest common divisor of two polynomials. The algorithm takes two polynomials . If the polynomial is zero, the result is , otherwise the result is the value the algorithm returns for pair . On each step the degree of the second argument decreases, so the algorithm works in finite number of steps. But how large that number could be? You are to answer this question.

You are given an integer n. You have to build two polynomials with degrees not greater than n, such that their coefficients are integers not exceeding 1 by their absolute value, the leading coefficients (ones with the greatest power of x) are equal to one, and the described Euclid's algorithm performs exactly n steps finding their greatest common divisor. Moreover, the degree of the first polynomial should be greater than the degree of the second. By a step of the algorithm we mean the transition from pair to pair .

假设你有两个多项式 和 。那么，多项式 可被唯一地表示为如下形式：

该表示可通过多项式长除法实现。此处， 表示多项式 $P(x)$ 的次数。 称为多项式 除以多项式 所得的余式，也记作 。

由于多项式可带余除法，我们便可定义用于求两个多项式最大公因式的欧几里得算法。该算法接收两个多项式 。若多项式 为零多项式，则结果为 ；否则，结果即为该算法在输入对 上所返回的值。每一步中，第二个参数的次数均严格下降，因此该算法必在有限步内终止。但该步数最多可能达到多少？你需要回答这一问题。

给定一个整数 $n$，你需要构造两个次数不超过 $n$ 的多项式，使其所有系数均为绝对值不超过 $1$ 的整数，且首项系数（即最高次幂 $x$ 的系数）均为 $1$，并使得上述欧几里得算法在计算它们的最大公因式时恰好执行 $n$ 步。此外，第一个多项式的次数须严格大于第二个多项式的次数。此处，算法的“一步”指从输入对 转换到输入对 的过程。

You are given a single integer n (1 ≤ n ≤ 150) — the number of steps of the algorithm you need to reach.

给你一个整数 $n$（$1 \leq n \leq 150$）——你需要执行该算法的步数。

Print two polynomials in the following format.

In the first line print a single integer m (0 ≤ m ≤ n) — the degree of the polynomial.

In the second line print m + 1 integers between  - 1 and 1 — the coefficients of the polynomial, from constant to leading.

The degree of the first polynomial should be greater than the degree of the second polynomial, the leading coefficients should be equal to 1. Euclid's algorithm should perform exactly n steps when called using these polynomials.

If there is no answer for the given n, print -1.

If there are multiple answer, print any of them.

按以下格式输出两个多项式。

第一行输出一个整数 $m$（$0 \le m \le n$）—— 多项式的次数。

第二行输出 $m + 1$ 个介于 $-1$ 和 $1$ 之间的整数 —— 多项式的系数，顺序为从常数项到最高次项。

第一个多项式的次数应严格大于第二个多项式的次数，且两个多项式的首项系数均须为 $1$。当使用这两个多项式作为输入调用欧几里得算法时，该算法应恰好执行 $n$ 步。

若对给定的 $n$ 不存在满足条件的解，请输出 $-1$。

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

In the second example you can print polynomials _x_2 - 1 and x. The sequence of transitions is

(_x_2 - 1, x) → (x,  - 1) → ( - 1, 0).

There are two steps in it.

在第二个例子中，你可以打印多项式 $x^2 - 1$ 和 $x$。变换序列为

$(x^2 - 1,\ x) \to (x,\ -1) \to (-1,\ 0)$。

该序列包含两步。