Problem: A sequence a0, a1, ... is called a recurrent binary sequence, if each term ai (i = 0, 1, ...) is equal to 0 or 1 and there exist coefficients <image> such that 

an = c1·an - 1 + c2·an - 2 + ... + ck·an - k (mod 2),  for all n ≥ k. Assume that not all of ci are zeros.

Note that such a sequence can be uniquely recovered from any k-tuple {as, as + 1, ..., as + 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 2k - 1, as k-tuple determines next element, and there are 2k - 1 non-zero k-tuples. Let us call a sequence long if its minimal period is exactly 2k - 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: c1, c2, ..., ck (coefficients). The second line should contain first k elements of the sequence: a0, a1, ..., ak - 1. All of them (elements and coefficients) should be equal to 0 or 1, and at least one ci has to be equal to 1.

If there are several solutions, output any.

Examples

Input

2


Output

1 1
1 0


Input

3


Output

0 1 1
1 1 1

Note

1. In the first sample: c1 = 1, c2 = 1, so an = an - 1 + an - 2 (mod 2). Thus the sequence will be:

<image>

so its period equals 3 = 22 - 1.

2. In the second sample: c1 = 0, c2 = 1, c3 = 1, so an = an - 2 + an - 3 (mod 2). Thus our sequence is:

<image>

and its period equals 7 = 23 - 1.

Periods are colored.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n;
struct Matrix {
  int a[55][55];
  Matrix operator*(const Matrix& b) const {
    Matrix ret;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        ret.a[i][j] = 0;
        for (int k = 0; k < n; ++k) ret.a[i][j] ^= a[i][k] & b.a[k][j];
      }
    return ret;
  }
  Matrix operator+(const Matrix& b) const {
    Matrix ret;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        ret.a[i][j] = a[i][j] ^ b.a[i][j];
      }
    return ret;
  }
  void create(int* b = 0) {
    if (b == 0) {
      for (int j = 0; j < n; ++j) a[0][j] = rand() & 1;
      a[0][n - 1] = 1;
    } else {
      for (int j = 0; j < n; ++j) a[0][j] = b[j];
    }
    for (int i = 1; i < n; ++i)
      for (int j = 0; j < n; ++j) a[i][j] = (int)(j == i - 1);
  }
  Matrix() {
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) a[i][j] = (int)(i == j);
  }
  Matrix(const Matrix& b) { memcpy(a, b.a, sizeof(a)); }
  Matrix& operator=(const Matrix& b) {
    memcpy(a, b.a, sizeof(a));
    return *this;
  }
  void print() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) printf("%d", a[i][j]);
      printf("\n");
    }
    printf("\n");
  }
  Matrix pow(long long k) {
    Matrix ret;
    Matrix b = *this;
    while (k > 0) {
      if (k & 1) ret = ret * b;
      b = b * b;
      k /= 2;
    }
    return ret;
  }
  bool is1() {
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (a[i][j] != (int)(i == j)) return false;
    return true;
  }
};
bool test(Matrix a) {
  long long k = (1LL << n) - 1;
  if (!a.pow(k).is1()) return false;
  for (long long d = 1; d * d <= k; ++d) {
    if (k % d == 0) {
      if (a.pow(d).is1()) return false;
      if (k / d != k && k / d != d) {
        if (a.pow(k / d).is1()) return false;
      }
    }
  }
  return true;
}
string res[] = {"11",
                "011",
                "1001",
                "00101",
                "101101",
                "1111101",
                "01100011",
                "010010101",
                "1011000001",
                "10110010011",
                "111000010101",
                "0010101100011",
                "01101111101011",
                "111011101101111",
                "1100001101111101",
                "01101100001110001",
                "100001101100110001",
                "1010101001110000111",
                "10110000101000010011",
                "111000011011011010101",
                "1001110011000010000111",
                "10001110110110111111101",
                "010011110000010010001101",
                "1011001001000011011001011",
                "10100111101010001001100111",
                "001001101101110010111111001",
                "1111011111010101001101000111",
                "11100010000100010110101111001",
                "010100110011010110101010010111",
                "1010001100011010110101111101101",
                "10111011110110101001101001111111",
                "010101110001111010111110011000111",
                "0000000110001010000001101111110011",
                "01001100011110111110111000110101001",
                "011111101011101000100010001101001111",
                "1111101000011100101010101111111100001",
                "10010101010000000101010011100000011001",
                "110110010111011101100001001111111001101",
                "1010010011010000010000100011110101001001",
                "00001011111110000100101101111101001001101",
                "111111000001011100010000001101001100001111",
                "0010011100011101000101101101101111010011011",
                "10110011011100001000000111111110111001100011",
                "011111000111100011101011011001001110010111001",
                "1110101000110101110000010101011000001110101111",
                "10101110001110100110000010100101011100011101011",
                "100010111110101010011000110001011010001011011001",
                "1000001101010101110100110000100100100000110011001",
                "00010101101110001001001001111010100011100100101101"};
int main() {
  n = 50;
  cin >> n;
  string ans = res[n - 2];
  for (int i = 0; i < n; ++i) printf("%c ", ans[i]);
  printf("\n");
  for (int i = 0; i < n; ++i) printf("1 ");
  return 0;
}