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

<image>

This can be done using [long division](https://en.wikipedia.org/wiki/Polynomial_long_division). Here, <image> denotes the degree of polynomial P(x). <image> is called the remainder of division of polynomial <image> by polynomial <image>, it is also denoted as <image>. 

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 <image>. If the polynomial <image> is zero, the result is <image>, otherwise the result is the value the algorithm returns for pair <image>. 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 <image> to pair <image>. 

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 x2 - 1 and x. The sequence of transitions is

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

There are two steps in it.

Difficulty: HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
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())
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=' ')


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))))


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
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]]))


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]
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=' ')


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])


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


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]))