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;
typedef bool matrix[64][64];
void mul(matrix a, matrix b, matrix c, int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      c[i][j] = false;
      for (int k = 0; k < n; k++) c[i][j] ^= a[i][k] && b[k][j];
    }
}
void pow(matrix a, matrix b, long long p, int n) {
  matrix c, d;
  memcpy(c, a, sizeof(matrix));
  memset(b, 0, sizeof(matrix));
  for (int i = 0; i < n; i++) b[i][i] = true;
  for (long long i = 1; i <= p; i <<= 1) {
    if (i & p) {
      mul(b, c, d, n);
      memcpy(b, d, sizeof(matrix));
    }
    mul(c, c, d, n);
    memcpy(c, d, sizeof(matrix));
  }
}
bool one(matrix a, int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (i == j && !a[i][j]) return false;
      if (i != j && a[i][j]) return false;
    }
  return true;
}
bool check(bool a[], int n) {
  long long m = (1LL << n) - 1, t = m;
  matrix b = {}, c;
  for (int i = 0; i < n; i++) b[0][i] = a[i];
  for (int i = 1; i < n; i++) b[i][i - 1] = true;
  pow(b, c, m, n);
  if (!one(c, n)) return false;
  for (long long i = 3; i * i <= m; i += 2) {
    if (m % i) continue;
    pow(b, c, t / i, n);
    if (one(c, n)) return false;
    while (m % i == 0) m /= i;
  }
  if (m != t) {
    pow(b, c, t / m, n);
    if (one(c, n)) return false;
  }
  return true;
}
void generate() {
  srand(time(NULL));
  for (int n = 2; n <= 50; n++) {
    while (true) {
      bool a[64];
      for (int i = 0; i < n; i++) a[i] = rand() % 2;
      if (check(a, n)) {
        putchar('\"');
        for (int i = 0; i < n; i++) putchar(a[i] ? '1' : '0');
        puts("\",");
        break;
      }
    }
  }
}
const char *ans[] = {"",
                     "1",
                     "11",
                     "101",
                     "0011",
                     "01111",
                     "110011",
                     "0100111",
                     "10001101",
                     "110000101",
                     "1000010011",
                     "00010011111",
                     "011101110101",
                     "0100100111111",
                     "00110111000001",
                     "100001111100011",
                     "0010110000111011",
                     "00101111000010101",
                     "100101011010000011",
                     "1100101110011000011",
                     "10101001010011001011",
                     "001101110011000111011",
                     "0100100011110001010101",
                     "00100101011100100011001",
                     "011011001011001010000001",
                     "0011000001000000110001011",
                     "11100001111011100000001001",
                     "100010111000110010000101101",
                     "0101100110100011000010011001",
                     "00010111111100110011111011111",
                     "110100011001000001010110100001",
                     "1100101001101011001000111010101",
                     "00101110011011110000111100110101",
                     "000001100000101011000010111010111",
                     "0110011011010111111110111011110011",
                     "10011101011101011100010101011110111",
                     "101101110000001001110011101110010001",
                     "0010111101011110101000010110101011001",
                     "10000100001001011010111111100011101101",
                     "110001011011100010100000101001001010001",
                     "0100111101011101110010110001100011011001",
                     "00010111111110110010110010010000011011011",
                     "101010011001101001001011001101000001010111",
                     "0001001010101111011111000011010000111000001",
                     "11011000000000110111100101001000110110100101",
                     "010101000010111001101100010010001010011100011",
                     "1001011111110010110011000111110011000110110111",
                     "00000011111111001111110010111000111111000000011",
                     "001001001000011000111010111000100100111001000101",
                     "0000111110001101001001000111001100001010011111011",
                     "00010101110101100111000011001010001011100101111011"};
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    if (i > 0) putchar(' ');
    putchar(ans[n][i]);
  }
  putchar('\n');
  putchar('1');
  for (int i = 1; i < n; i++) printf(" 0");
  putchar('\n');
  return 0;
}