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

Solution:
import java.io.*;

import java.awt.geom.Point2D;
import java.text.*;
import java.math.*;
import java.util.*;

public class Main implements Runnable {

	final String filename = "";

	String[] ans = new String[] { "1", "11", "011", "0011", "00101", "000011",
			"0000011", "00011101", "000010001", "0000001001", "00000000101",
			"000001010011", "0000000011011", "00000000101011",
			"000000000000011", "0000000000101101", "00000000000001001",
			"000000000000100111", "0000000000000100111",
			"00000000000000001001", "000000000000000000101",
			"0000000000000000000011", "00000000000000000100001",
			"000000000000000000011011", "0000000000000000000001001",
			"00000000000000000001000111", "000000000000000000000100111",
			"0000000000000000000000001001", "00000000000000000000000000101",
			"000000000000000000000001010011",
			"0000000000000000000000000001001",
			"00000000000000000000000010101111",
			"000000000000000000000000001010011",
			"0000000000000000000000000011100111",
			"00000000000000000000000000000000101",
			"000000000000000000000000000001110111",
			"0000000000000000000000000000000111111",
			"00000000000000000000000000000001100011",
			"000000000000000000000000000000000010001",
			"0000000000000000000000000000000000111001",
			"00000000000000000000000000000000000001001",
			"000000000000000000000000000000000000111111",
			"0000000000000000000000000000000000001011001",
			"00000000000000000000000000000000000001100101",
			"000000000000000000000000000000000000000011011",
			"0000000000000000000000000000000000000100101111",
			"00000000000000000000000000000000000000000100001",
			"000000000000000000000000000000000000000010110111",
			"0000000000000000000000000000000000000000001110001",
			"00000000000000000000000000000000000000000000011101" };

	int[][] mult(int[][] a, int[][] b) {
		int n = a.length;
		int[][] res = new int[n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				for (int k = 0; k < n; k++) {
					res[i][k] ^= a[i][j] & b[j][k];
				}
		return res;
	}

	int[][][] pows;

	int[][] pow(long k) {
		int n = pows[0].length;
		int[][] res = new int[n][n];
		for (int i = 0; i < n; i++)
			res[i][i] = 1;
		int i = 0;
		while (k > 0) {
			if (k % 2 == 1)
				res = mult(res, pows[i]);
			k /= 2;
			i++;
		}
		return res;
	}

	long smart(int k) {
		long[] divs = new long[10000];
		int dc = 0;
		long p2 = (1L << k) - 1;
		for (int i = 2; i * (long) i <= p2; i++) {
			if (p2 % i == 0) {
				divs[dc++] = i;
				divs[dc++] = p2 / i;
			}
		}
		cycle: for (long b = 1; b <= p2; b += 2) {
			int[][] matrix = new int[k][k];
			for (int i = 1; i < k; i++)
				matrix[i][i - 1] = 1;
			for (int i = 0; i < k; i++)
				matrix[0][i] = ((b & (1L << (k - (long) i - 1))) > 0) ? 1 : 0;

			pows = new int[k][k][k];
			pows[0] = matrix;
			for (int i = 1; i < k; i++)
				pows[i] = mult(pows[i - 1], pows[i - 1]);
			int[][] r = pow(p2);
			for (int a = 0; a < k; a++) {
				for (int c = 0; c < k; c++) {
					if ((r[a][c] == 1) ^ (a == c))
						continue cycle;
				}
			}

			cycle2: for (int i = 0; i < dc; i++) {
				r = pow(divs[i]);
				for (int a = 0; a < k; a++) {
					for (int c = 0; c < k; c++) {
						if ((r[a][c] == 1) ^ (a == c))
							continue cycle2;
					}
				}
				continue cycle;
			}
			return b;
		}
		return -1;
	}

	public void solve() throws Exception {
		// for (int k = 2; k <= 10; k++) {
		// System.out.println("k=" + k);
		// boolean[] was = new boolean[1 << k];
		// String s = "";
		// for (int b = 1; b < 1 << k; b++) {
		// int cnt = 0;
		// Arrays.fill(was, false);
		// int a = 1;
		// while (a != 0 && !was[a]) {
		// was[a] = true;
		// cnt++;
		// int c = 0;
		// for (int i = 0; i < k; i++)
		// if ((a & (1 << i)) > 0 && (b & (1 << i)) > 0)
		// c ^= 1;
		// a = (c << (k - 1)) + (a >> 1);
		// }
		// if (cnt == (1 << k) - 1) {
		// s = Integer.toString(b, 2);
		// while (s.length() < k)
		// s = "0" + s;
		// System.out.println(s);
		// break;
		// }
		// }
		// s = Long.toString(smart(k), 2);
		// while (s.length() < k)
		// s = "0" + s;
		// System.out.println(s);
		// }

		// for (int k = 1; k <= 50; k++) {
		// String s = Long.toString(smart(k), 2);
		// while (s.length() < k)
		// s = "0" + s;
		// System.out.println("\"" + s + "\",");
		// }

		int k = iread();
		for (int i = 0; i < k; i++) {
			out.write(ans[k-1].charAt(i));
			if (i == k - 1)
				out.write("\n");
			else
				out.write(" ");
		}
		out.write("1");
		for (int i = 1; i < k; i++)
			out.write(" 0");
		out.write("\n");
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedWriter(new OutputStreamWriter(System.out));
			// in = new BufferedReader(new FileReader(filename+".in"));
			// out = new BufferedWriter(new FileWriter(filename+".out"));
			solve();
			out.flush();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public int iread() throws Exception {
		return Integer.parseInt(readword());
	}

	public double dread() throws Exception {
		return Double.parseDouble(readword());
	}

	public long lread() throws Exception {
		return Long.parseLong(readword());
	}

	BufferedReader in;

	BufferedWriter out;

	public String readword() throws IOException {
		StringBuilder b = new StringBuilder();
		int c;
		c = in.read();
		while (c >= 0 && c <= ' ')
			c = in.read();
		if (c < 0)
			return "";
		while (c > ' ') {
			b.append((char) c);
			c = in.read();
		}
		return b.toString();
	}

	public static void main(String[] args) {
		try {
			Locale.setDefault(Locale.US);
		} catch (Exception e) {

		}
		// new Thread(new Main()).start();
		new Thread(null, new Main(), "1", 1 << 25).start();
	}
}