Допустим, у вас есть два многочлена 
и 
. Тогда многочлен 
можно единственным образом представить в виде
Это может быть сделано делением в столбик. В этой записи 
обозначает степень многочлена P(x). 
при этом будем называть остатком от деления многочлена на многочлен 
и обозначать 
.
Раз есть способ разделить один многочлен на другой с остатком, то можно определить и алгоритм Евклида для нахождения наибольшего общего делителя двух многочленов. Алгоритм определён таким образом, что он принимает пару многочленов 
, а затем если многочлен нулевой, то алгоритм возвращает многочлен , а иначе возвращает результат выполнения алгоритма для пары 
. На каждом шаге степень второго аргумента уменьшается, поэтому алгоритм отработает за конечное число шагов. Но насколько большим оно может быть? Это вам и предстоит выяснить.
Вам дано число n. Вам нужно вывести два многочлена степени не выше n таких, что их коэффициенты — целые числа, не превышающие 1 по абсолютной величине, при этом старший коэффициент (при максимальной степени x) должен быть равен единице, и вычисление их наибольшего общего делителя потребует ровно n шагов алгоритма Евклида. Кроме того, степень первого многочлена должна быть больше степени второго. Шагом алгоритма Евклида мы называем переход от к .
Выходные данные
Выведите два многочлена в следующем формате.
В первой строке выведите число m (0 ≤ m ≤ n) — степень многочлена.
Во второй строке выведите m + 1 целых чисел от - 1 до 1 — коэффициенты многочлена, от младшего к старшему.
Степень первого многочлена должна быть больше степени второго, а старшие коэффициенты обоих многочленов должны быть равны 1. Алгоритм Евклида, вызванный от этих многочленов должен занимать ровно n шагов.
Если для данного числа n ответа не существует, выведите -1.
Если есть несколько возможных вариантов ответа, выведите любой из них.
Примечание
Во втором тестовом примере можно вывести многочлены x2 - 1 и x. Тогда цепочка вызовов будет
(x2 - 1, x) → (x, - 1) → ( - 1, 0).Она состоит из ровно двух шагов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
0 1
0
1
|
|
2
|
2
|
2
-1 0 1
1
0 1
|