Suppose you have two polynomials $A(x) = \sum_{k = 0}^{n} a_{k} x^{k}$ and $B(x) = \sum_{k = 0}^{m} b_{k} x^{k}$. Then polynomial $A(x)$ can be uniquely represented in the following way:$A(x) = B(x) \cdot D(x) + R(x), \operatorname{deg} R(x) < \operatorname{deg} B(x)$

This can be done using long division. Here, $\operatorname{deg} P(x)$ denotes the degree of polynomial P(x). $R(x)$ is called the remainder of division of polynomial $A(x)$ by polynomial $B(x)$, it is also denoted as $A \operatorname{mod} B$. 

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 $(A, B)$. If the polynomial $B(x)$ is zero, the result is $A(x)$, otherwise the result is the value the algorithm returns for pair $(B, A \operatorname{mod} B)$. 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 $(A, B)$ to pair $(B, A \operatorname{mod} B)$. 


-----Input-----

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


-----Output-----

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.


-----Examples-----
Input
1

Output
1
0 1
0
1

Input
2

Output
2
-1 0 1
1
0 1



-----Note-----

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.

Difficulty: HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
n = int(input())
A = [1]
B = []
for _ in range(n):
	new_A = [0] + A[:]
	new_B = A[:]
	for (i, b) in enumerate(B):
		new_A[i] += b
	A = [a % 2 for a in new_A]
	B = [b % 2 for b in new_B]
print(len(A) - 1)
print(*A)
print(len(B) - 1)
print(*B)


n = int(input())

def print_poly(a):
	print(len(a) - 1)
	print(' '.join(map(str, a)))

def shift_add(a, mul, b):
	c = [0] * (len(a) + 1)
	for i in range(len(a)):
		c[i + 1] = a[i] * mul
	for i in range(len(b)):
		c[i] += b[i]
	return c
a = [0, 1]
b = [1]
for i in range(n - 1):
	c = shift_add(a, 1, b)
	if max(c) <= 1 and min(c) >= -1:
		(a, b) = (c, a)
	else:
		c = shift_add(a, -1, b)
		if max(c) <= 1 and min(c) >= -1:
			(a, b) = (c, a)
		else:
			print('> <')
if a[-1] == -1:
	a = list([-x for x in a])
if b[-1] == -1:
	b = list([-x for x in b])
print_poly(a)
print_poly(b)


f = [[1], [0, 1]]
n = int(input())
for i in range(2, n + 1):
	l = [0] + f[i - 1]
	for j in range(len(f[i - 2])):
		l[j] = l[j] + f[i - 2][j] & 1
	f.append(l)
print(n)
print(*f[n])
print(n - 1)
print(*f[n - 1])


import sys
f = sys.stdin
n = f.readline()
n = int(n)
t = [[0], [1]]
for j in range(n):
	cur = [0] + t[-1]
	for (i, x) in enumerate(t[-2]):
		cur[i] += x
	if min(cur) < -1 or max(cur) > 1:
		cur = [0] + t[-1]
		for (i, x) in enumerate(t[-2]):
			cur[i] -= x
	t.append(cur)
print(len(t[n + 1]) - 1)
print(' '.join([str(x) for x in t[n + 1]]))
print(len(t[n]) - 1)
print(' '.join([str(x) for x in t[n]]))


n = int(input())
p = [[1], [0, 1]]
for i in range(n - 1):
	t = [0] + p[-1]
	for j in range(len(p[i])):
		t[j] ^= p[i][j]
	p.append(t)
print(n)
print(*p[n])
print(n - 1)
print(*p[-2])


import sys
inp = sys.stdin.readline
input = lambda : inp().strip()
flush = sys.stdout.flush

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():
	n = iin()
	ans = [0] * (n + 1)
	ans[0] = 1
	ans1 = [0] * (n + 1)
	sol = 0
	for i in range(n):
		su = ans1[:]
		for j in range(n):
			su[j + 1] += ans[j]
			if su[j + 1] > 1:
				su[j + 1] = 0
		(ans, ans1) = (su, ans)
	if sol:
		print(-1)
	else:
		(m1, m2) = (0, 0)
		for i in range(n + 1):
			if abs(ans[i]):
				m1 = i + 1
			if abs(ans1[i]):
				m2 = i + 1
		print(m1 - 1)
		print(*ans[:m1])
		print(m2 - 1)
		print(*ans1[:m2])
main()


n = int(input())
a = [1, 2]
for i in range(n - 1):
	a.append(2 * a[-1] ^ a[-2])
print(n)
d = 0
while 2 ** d <= a[-1]:
	if a[-1] & 2 ** d == 0:
		print(0, end=' ')
	else:
		print(1, end=' ')
	d += 1
print()
print(n - 1)
d = 0
while 2 ** d <= a[-2]:
	if a[-2] & 2 ** d == 0:
		print(0, end=' ')
	else:
		print(1, end=' ')
	d += 1


a_coeffs = [1, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, -1, 0, 0, 0, 1]
b_coeffs = [1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, -1, 0]

def rem(a, b):
	assert len(a) == len(b) + 1
	coeff = a[0] * b[0]
	if a[0] == -1:
		a = [-c for c in a]
	if b[0] == -1:
		b = [-c for c in b]
	b = b + [0]
	assert len(a) == len(b)
	r = [c1 - c2 for (c1, c2) in zip(a, b)]
	assert r[0] == 0 and r[1] == 0 and (r[2] != 0)
	r = r[2:]
	r = [coeff * c for c in r]
	return r

def solve(n):
	(a, b) = (a_coeffs, b_coeffs)
	for _ in range(n, 150):
		(a, b) = (b, rem(a, b))
	if a[0] == -1:
		a = [-c for c in a]
	if b[0] == -1:
		b = [-c for c in b]
	return (a, b)
n = int(input())
(a, b) = solve(n)
print(len(a) - 1)
print(' '.join((str(c) for c in reversed(a))))
print(len(b) - 1)
print(' '.join((str(c) for c in reversed(b))))


class polynomial:

	def __init__(self, data):
		self.data = data

	def __lshift__(self, x):
		return polynomial([0] * x + self.data)

	def __len__(self):
		return len(self.data)

	def __sub__(self, other):
		newData = [y - x for (y, x) in zip(self.data, other.data + [0] * 1000)]
		while len(newData) > 0 and newData[-1] == 0:
			del newData[-1]
		return polynomial(newData)

	def __add__(self, other):
		newData = [(y + x) % 2 for (y, x) in zip(self.data + [0] * 1000, other.data + [0] * 1000)]
		while len(newData) > 0 and newData[-1] == 0:
			del newData[-1]
		return polynomial(newData)

	def __mul__(self, amt):
		return polynomial([x * amt for x in self.data])

	def __getitem__(self, idx):
		return self.data[idx]

	def __mod__(self, other):
		tmp = self
		times = 0
		while len(tmp) >= len(other):
			times += 1
			if times > 1000:
				print(*tmp.data)
				print(*other.data)
				exit(0)
			tmp = tmp - (other << len(tmp) - len(other)) * (tmp[-1] // other[-1])
		return tmp

def gcdSteps(p1, p2, steps=0):
	if len(p1) == 0 or len(p2) == 0:
		return steps
	else:
		return gcdSteps(p2, p1 % p2, steps + 1)
(a, b) = (polynomial([0, 1]), polynomial([1]))
for i in range(int(input()) - 1):
	if gcdSteps(a, b) != i + 1:
		print('error', i)
	(a, b) = (b + (a << 1), a)
print(len(a) - 1)
print(*a.data)
print(len(b) - 1)
print(*b.data)


n = int(input())
c = [0, 1]
p = [1]
for i in range(1, n):
	nc = [0] + c
	rev = False
	for j in range(len(p)):
		nc[j] -= p[j]
		if abs(nc[j]) > 1:
			rev = True
	if rev:
		for j in range(len(p)):
			nc[j] += 2 * p[j]
			if abs(nc[j]) > 1:
				rev = True
	p = c
	c = nc
print(len(c) - 1)
print(' '.join([str(i) for i in c]))
print(len(p) - 1)
print(' '.join([str(i) for i in p]))


def ii():
	return int(input())

def mi():
	return list(map(int, input().split()))

def li():
	return list(mi())
n = ii()

def gen(p, q, r):
	x = [0, p]
	y = [q]
	for c in range(1, n):
		nx = [0] + [-xi for xi in x]
		px = [0] + x
		if r:
			(nx, px) = (px, nx)
		bad = 0
		for i in range(len(y)):
			px[i] += y[i]
			if abs(px[i]) > 1:
				bad = 1
				break
		if not bad:
			(x, y) = (px, x)
			continue
		bad = 0
		for i in range(len(y)):
			nx[i] += y[i]
			if abs(nx[i]) > 1:
				bad = 1
				break
		if not bad:
			(x, y) = (nx, x)
			continue
		print('OH NO')
		z = 1 / 0
	return (x, y)
found = 0
for (i, j) in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
	for r in [0, 1]:
		(x, y) = gen(i, j, r)
		if x[-1] == 1 and y[-1] == 1:
			found = 1
			break
	if found:
		break
if not found:
	print(n, 'OH NO!!')
print(len(x) - 1)
print(*x)
print(len(y) - 1)
print(*y)


n = int(input())
a = [1]
b = [0]
for i in range(n):
	c = a.copy()
	a.append(0)
	for i in range(len(a) - 1, 0, -1):
		a[i] = a[i - 1]
		if i < len(b):
			a[i] += b[i]
		a[i] %= 2
	a[0] = b[0]
	b = c.copy()
print(len(a) - 1)
for i in a:
	print(i, end=' ')
print('')
print(len(b) - 1)
for i in b:
	print(i, end=' ')


B = [1, 0]
R = [1]
A = list(B)
n = int(input())
for i in range(1, n):
	A += [0]
	for j in range(-1, -len(R) - 1, -1):
		A[len(A) + j] += R[len(R) + j]
		if A[len(A) + j] == 2:
			A[len(A) + j] = 0
	R = list(B)
	B = list(A)
print(len(B) - 1)
for u in reversed(B):
	print(u, end=' ')
print()
print(len(R) - 1)
for u in reversed(R):
	print(u, end=' ')
print()


import sys
n = int(sys.stdin.readline().split()[0])

class Polynomial:

	def __init__(self, coef):
		first_nonzero = False
		index = len(coef) - 1
		while not first_nonzero:
			if not coef[index] == 0:
				first_nonzero = True
			elif index == 0:
				first_nonzero = True
			else:
				index -= 1
		self.degree = index
		self.coef = [coef[j] for j in range(index + 1)]

	def multiply_by_x(self):
		new_coef = [0]
		for j in range(self.degree + 1):
			new_coef.append(self.coef[j])
		return Polynomial(new_coef)

	def minus(self):
		new_coef = [-self.coef[j] for j in range(self.degree + 1)]
		return Polynomial(new_coef)

	def add(self, other):
		other_coef = other.coef
		new_coef = [0 for j in range(max(self.degree, other.degree) + 1)]
		m = min(self.degree, other.degree)
		M = max(self.degree, other.degree)
		if self.degree > other.degree:
			bigger_poly = self
		else:
			bigger_poly = other
		for j in range(m + 1):
			new_coef[j] = self.coef[j] + other.coef[j]
		for j in range(m + 1, M + 1):
			new_coef[j] = bigger_poly.coef[j]
		return Polynomial(new_coef)

	def is_legal(self):
		result = True
		bools = [None for j in range(self.degree + 1)]
		bools[self.degree] = self.coef[self.degree] == 1
		for j in range(self.degree):
			bools[j] = self.coef[j] == 0 or self.coef[j] == 1 or self.coef[j] == -1
		for j in range(self.degree + 1):
			result = result and bools[j]
		return result

	def print(self):
		output = ''
		for j in range(self.degree + 1):
			output += str(self.coef[j]) + ' '
		print(output)
f = []
f.append(Polynomial([1]))
f.append(Polynomial([0, 1]))
for j in range(2, 151):
	xf = f[j - 1].multiply_by_x()
	t_1 = xf.add(f[j - 2])
	t_2 = xf.add(f[j - 2].minus())
	if t_1.is_legal():
		f.append(t_1)
	elif t_2.is_legal():
		f.append(t_2)
print(f[n].degree)
f[n].print()
print(f[n - 1].degree)
f[n - 1].print()


n = int(input())
(a, b) = ([1], [0])
for i in range(n):
	new_b = a[:]
	a1 = a[:]
	a2 = a[:]
	a1.append(0)
	a2.append(0)
	for i in range(-1, -len(b) - 1, -1):
		a1[i] += b[i]
	for i in range(-1, -len(b) - 1, -1):
		a2[i] -= b[i]
	if max([abs(kek) for kek in a1]) < 2:
		a = a1
	elif max([abs(kek) for kek in a2]) < 2:
		a = a2
	else:
		print('oops')
		exit(0)
	b = new_b
print(len(a) - 1)
print(*a[::-1])
print(len(b) - 1)
print(*b[::-1])


n = int(input())
A = [0 for i in range(n + 1)]
B = [0 for i in range(n + 1)]
A[0] = 1
for i in range(n):
	temp = A[:]
	for j in reversed(range(1, n + 1)):
		A[j] = (A[j - 1] + B[j]) % 2
	A[0] = B[0]
	B = temp
print(n)
for i in range(n):
	print(A[i], end=' ')
print(A[n])
print(n - 1)
for i in range(n):
	print(B[i], end=' ')


n = int(input())
a = [1]
b = []
for _ in range(n):
	c = [0] + a[:]
	d = a[:]
	for (i, u) in enumerate(b):
		c[i] += u
	a = [u % 2 for u in c]
	b = [u % 2 for u in d]
print(len(a) - 1)
print(*a)
print(len(b) - 1)
print(*b)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def construct(n):
	A = [1]
	B = [0]
	for i in range(n):
		next_A1 = [0 for j in range(len(A) + 1)]
		next_A2 = [0 for j in range(len(A) + 1)]
		next_B = [A[j] for j in range(len(A))]
		for j in range(len(A)):
			next_A1[j + 1] = A[j]
			next_A2[j + 1] = -A[j]
		for j in range(len(B)):
			next_A1[j] += B[j]
			next_A2[j] += B[j]
		if max((abs(a) for a in next_A1)) <= 1:
			A = next_A1
		else:
			assert max((abs(a) for a in next_A2)) <= 1
			A = next_A2
		B = next_B
	return (A, B)
N = int(input())
(A, B) = construct(N)
if A[-1] == -1:
	for i in range(len(A)):
		A[i] *= -1
if B[-1] == -1:
	for i in range(len(B)):
		B[i] *= -1
print(len(A) - 1)
print(*A)
print(len(B) - 1)
print(*B)


from random import getrandbits as R
rb = lambda : R(1)

def modu(p, q):
	if len(q) == 1:
		return [0]
	p = p[:]
	for d in range(len(p) - 1, len(q) - 2, -1):
		a = p.pop()
		b = q[-1]
		B = [-k * a / b for k in q[:-1]]
		for i in range(len(B)):
			p[i + 1 + len(p) - 1 - (len(q) - 1)] += B[i]
	while len(p) > 1 and abs(p[-1]) < 1e-06:
		p.pop()
	return p

def gcd(p, q):
	if len(q) == 1 and abs(q[0]) < 1e-06:
		return (p, 1)
	else:
		(p, iters) = gcd(q, modu(p, q))
		return (p, iters + 1)
for n in [int(input())]:
	while True:
		p = [1] * (n + 1)
		q = [1] * n
		for i in range(n):
			p[i] = rb()
		for i in range(n - 1):
			q[i] = rb()
		(Q, iters) = gcd(p, q)
		if iters < n + 1:
			continue
		print(len(p) - 1)
		print(*p)
		print(len(q) - 1)
		print(*q)
		break