A sequence $*a*_{0}, *a*_{1}, ...$ is called a recurrent binary sequence, if each term $*a*_{*i*}$ $(*i* = 0, 1, ...)$ is equal to 0 or 1 and there exist coefficients such that

$*a*_{*n*} = *c*_{1}·*a*_{*n* - 1} + *c*_{2}·*a*_{*n* - 2} + ... + *c*_{*k*}·*a*_{*n* - *k*} (*mod* 2),$

for all

n ≥ k

. Assume that not all of

c_i

are zeros.

Note that such a sequence can be uniquely recovered from any $*k*$-tuple ${*a*_{*s*}, *a*_{*s* + 1}, ..., *a*_{*s* + *k* - 1}}$ and so it is periodic. Moreover, if a $*k*$-tuple contains only zeros, then the sequence contains only zeros, so this case is not very interesting. Otherwise the minimal period of the sequence is not greater than $2^{*k*} - 1$, as $*k*$-tuple determines next element, and there are $2^{*k*} - 1$ non-zero $*k*$-tuples. Let us call a sequence long if its minimal period is exactly $2^{*k*} - 1$. Your task is to find a long sequence for a given $*k*$, if there is any.

Input

Input contains a single integer $*k*$ ($2 ≤ *k* ≤ 50$).

Output

If there is no long sequence for a given $*k*$, output "-1" (without quotes). Otherwise the first line of the output should contain $*k*$ integer numbers: $*c*_{1}, *c*_{2}, ..., *c*_{*k*}$ (coefficients). The second line should contain first $*k*$ elements of the sequence: $*a*_{0}, *a*_{1}, ..., *a*_{*k* - 1}$. All of them (elements and coefficients) should be equal to 0 or 1, and at least one $*c*_{*i*}$ has to be equal to 1.

If there are several solutions, output any.

Note

1. In the first sample: $*c*_{1} = 1$, $*c*_{2} = 1$, so $*a*_{*n*} = *a*_{*n* - 1} + *a*_{*n* - 2} (*mod* 2)$. Thus the sequence will be:

so its period equals $3 = 2^{2} - 1$.

2. In the second sample: $*c*_{1} = 0$, $*c*_{2} = 1$, $*c*_{3} = 1$, so $*a*_{*n*} = *a*_{*n* - 2} + *a*_{*n* - 3} (*mod* 2)$. Thus our sequence is:

and its period equals $7 = 2^{3} - 1$.

Periods are colored.