{"raw_statement":[{"iden":"statement","content":"Suppose you have two polynomials and . Then polynomial can be uniquely represented in the following way:\n\nThis can be done using [long division](https://en.wikipedia.org/wiki/Polynomial_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 .\n\nSince 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.\n\nYou 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 ."},{"iden":"input","content":"You are given a single integer _n_ (1 ≤ _n_ ≤ 150) — the number of steps of the algorithm you need to reach."},{"iden":"output","content":"Print two polynomials in the following format.\n\nIn the first line print a single integer _m_ (0 ≤ _m_ ≤ _n_) — the degree of the polynomial.\n\nIn the second line print _m_ + 1 integers between  - 1 and 1 — the coefficients of the polynomial, from constant to leading.\n\nThe 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.\n\nIf there is no answer for the given _n_, print _\\-1_.\n\nIf there are multiple answer, print any of them."},{"iden":"examples","content":"Input\n\n1\n\nOutput\n\n1\n0 1\n0\n1\n\nInput\n\n2\n\nOutput\n\n2\n-1 0 1\n1\n0 1"},{"iden":"note","content":"In the second example you can print polynomials _x_2 - 1 and _x_. The sequence of transitions is\n\n<center>(_x_2 - 1, _x_) → (_x_,  - 1) → ( - 1, 0).</center>There are two steps in it."}],"translated_statement":[{"iden":"statement","content":"假设你有两个多项式 $P(x)$ 和 $Q(x)$。那么多项式 $P(x)$ 可以唯一地表示为以下形式：\n\n$$\nP(x) = Q(x) \\cdot D(x) + R(x)\n$$\n\n这可以通过长除法完成。这里，$\\deg(P(x))$ 表示多项式 $P(x)$ 的次数。$R(x)$ 称为 $P(x)$ 除以 $Q(x)$ 的余数，也记作 $P(x) \\bmod Q(x)$。\n\n由于存在带余数的多项式除法，我们可以定义求两个多项式最大公因式的欧几里得算法。该算法接受两个多项式 $(P(x), Q(x))$。如果多项式 $Q(x)$ 为零，则结果为 $P(x)$；否则，结果为算法对数对 $(Q(x), P(x) \\bmod Q(x))$ 返回的值。在每一步中，第二个参数的次数都会减少，因此算法在有限步内终止。但这个步数最多能有多大？你需要回答这个问题。\n\n给你一个整数 $n$。你需要构造两个多项式，它们的次数不超过 $n$，系数为绝对值不超过 $1$ 的整数，首项系数（即最高次幂对应的系数）为 $1$，且上述欧几里得算法在求它们的最大公因式时恰好执行 $n$ 步。此外，第一个多项式的次数应大于第二个多项式的次数。这里的“一步”指从数对 $(P(x), Q(x))$ 转换到 $(Q(x), P(x) \\bmod Q(x))$。\n\n你将获得一个整数 $n$（$1 \\leq n \\leq 150$）——你需要达到的算法步数。\n\n请按以下格式输出两个多项式：\n\n第一行输出一个整数 $m$（$0 \\leq m \\leq n$）——多项式的次数。\n\n第二行输出 $m + 1$ 个介于 $-1$ 和 $1$ 之间的整数——按常数项到首项的顺序排列的多项式系数。\n\n第一个多项式的次数必须大于第二个多项式的次数，且两个多项式的首项系数必须为 $1$。欧几里得算法在使用这两个多项式时必须恰好执行 $n$ 步。\n\n如果给定 $n$ 无解，请输出 _-1_。\n\n如果有多个解，输出任意一个即可。\n\n在第二个例子中，你可以输出多项式 $x^2 - 1$ 和 $x$。其变换序列为\n\n$$(x^2 - 1, x) \\to (x, -1) \\to (-1, 0)$$\n\n共两步。"},{"iden":"input","content":"你将获得一个整数 $n$（$1 \\leq n \\leq 150$）——你需要达到的算法步数。"},{"iden":"output","content":"请按以下格式输出两个多项式：第一行输出一个整数 $m$（$0 \\leq m \\leq n$）——多项式的次数。第二行输出 $m + 1$ 个介于 $-1$ 和 $1$ 之间的整数——按常数项到首项的顺序排列的多项式系数。第一个多项式的次数必须大于第二个多项式的次数，且两个多项式的首项系数必须为 $1$。欧几里得算法在使用这两个多项式时必须恰好执行 $n$ 步。如果给定 $n$ 无解，请输出 _-1_。如果有多个解，输出任意一个即可。"},{"iden":"examples","content":"输入1输出10 101输入2输出2-1 0 110 1"},{"iden":"note","content":"在第二个例子中，你可以输出多项式 $x^2 - 1$ 和 $x$。其变换序列为\n\n$$(x^2 - 1, x) \\to (x, -1) \\to (-1, 0)$$\n\n共两步。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 150 $.  \nLet $ P(x), Q(x) \\in \\mathbb{Z}[x] $ be two polynomials such that:  \n- $ \\deg(P) > \\deg(Q) $,  \n- $ \\deg(P) \\leq n $, $ \\deg(Q) \\leq n $,  \n- Leading coefficients of $ P(x) $ and $ Q(x) $ are 1,  \n- All coefficients of $ P(x) $ and $ Q(x) $ lie in $ \\{-1, 0, 1\\} $.  \n\n**Constraints**  \nThe Euclidean algorithm for polynomials, defined by the recurrence:  \n$$\n\\begin{cases}\nR_0 = P, \\\\\nR_1 = Q, \\\\\nR_{i} = R_{i-2} \\mod R_{i-1} \\quad \\text{for } i \\geq 2,\n\\end{cases}\n$$  \nperforms exactly $ n $ steps before reaching $ R_n = 0 $, i.e., $ R_{n-1} \\neq 0 $ and $ R_n = 0 $.  \n\n**Objective**  \nConstruct such $ P(x) $ and $ Q(x) $ satisfying the above, or output $-1$ if no such pair exists.  \n\n**Output Format**  \n- First polynomial: degree $ m_1 $, then $ m_1 + 1 $ coefficients from constant to leading.  \n- Second polynomial: degree $ m_2 $, then $ m_2 + 1 $ coefficients from constant to leading.  \nWith $ m_1 > m_2 $, leading coefficients = 1, all coefficients in $ \\{-1, 0, 1\\} $.","simple_statement":null,"has_page_source":false}