STATEMENT

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

This is the Euclid’s algorithm for finding the gcd of two numbers.
Now, suppose instead of integers we take a(x) and b(x) as polynomials. Given N, you need to find two polynomials a(x) and b(x) such that, for finding the gcd of the polynomials the Euclid’s function goes upto N steps.

The polynomials must satisfy the following properties-
1- Degree of a(x) should be greater than degree of b(x).
2- All the coefficients should be either 0 or 1.
3- Degree of a(x) and b(x) should not be greater than N.

INPUT

The only line of input contains single integer N.

OUTPUT

Print two polynomials a(x) and b(x) in the following format.
In the first line print a single integer m (0 ≤ m ≤ N), degree of the polynomial.
In the second line print m + 1 integers either 0 or 1, coefficients of the polynomial, from constant to leading. Similarly, print the second polynomial b(x) in next two lines. If there is no answer for the given N, print "-1".

CONSTRAINTS

1<=N<=200