Problem: In this problem you have to build tournament graph, consisting of n vertices, such, that for any oriented pair of vertices (v, u) (v ≠ u) there exists a path from vertex v to vertex u consisting of no more then two edges.

A directed graph without self-loops is a tournament, if there is exactly one edge between any two distinct vertices (in one out of two possible directions).

Input

The first line contains an integer n (3 ≤ n ≤ 1000), the number of the graph's vertices.

Output

Print -1 if there is no graph, satisfying the described conditions.

Otherwise, print n lines with n integers in each. The numbers should be separated with spaces. That is adjacency matrix a of the found tournament. Consider the graph vertices to be numbered with integers from 1 to n. Then av, u = 0, if there is no edge from v to u, and av, u = 1 if there is one. 

As the output graph has to be a tournament, following equalities must be satisfied: 

  * av, u + au, v = 1 for each v, u (1 ≤ v, u ≤ n; v ≠ u); 
  * av, v = 0 for each v (1 ≤ v ≤ n). 

Examples

Input

3


Output

0 1 0
0 0 1
1 0 0


Input

4


Output

-1

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class b {
	static PrintWriter out;
public static void main(String[] args) throws IOException {
	input.init(System.in);
	out = new PrintWriter(System.out);
	int n = input.nextInt();
	
	if(n == 4)
	{
		out.println(-1);
		out.close();
		return;
	}
	else if(n%2 == 0)
	{
		int[][] a = new int[n][n];
		for(int i = 0; i<n; i++)
		{
			for(int j = i+1; j<n; j++)
			{
				a[i][j] = (i+j)%2;
				if(i == n-4 && j == n-1) a[i][j] ^= 1;
				a[j][i] = 1 - a[i][j];
			}
		}
		for(int i = 0; i<n; i++)
		{
			for(int j = 0; j<n; j++) out.print(a[i][j]+" ");
			out.println();
		}
		//boolean b = go(n, 0, 0, new int[n][n]);
		//out.println(b);
		out.close();
		return;
	}
	int[][] a = new int[n][n];
	for(int i = 0; i<n; i++)
	{
		for(int j = 1; j<n; j+=2)
		{
			a[i][(i+j)%n] = 1;
		}
	}
	for(int i = 0; i<n; i++)
	{
		for(int j = 0; j<n; j++) out.print(a[i][j]+" ");
		out.println();
	}
	out.close();
}
static int count = 0;
static boolean go(int n, int r, int c, int[][] g)
{
	if(r == n)
	{
		int[][] copy = new int[n][n];
		for(int i = 0; i<n; i++)
			for(int j = 0; j<n; j++)
				copy[i][j] = g[i][j];
		for(int k = 0; k<n; k++)
			for(int i = 0; i<n; i++)
				for(int j = 0; j<n; j++)
				{
					if(copy[i][k] == 0 || copy[k][j] == 0) continue;
					if(copy[i][j] == 0 || copy[i][k] + copy[k][j] < copy[i][j]) copy[i][j] = copy[i][k] + copy[k][j];
				}
		boolean good = true;
		for(int i = 0; i<n; i++)
			for(int j = 0; j<n; j++)
				if(i != j) good &= copy[i][j] != 0 && copy[i][j] <= 2;
		if(good)
		{
			//System.out.println("FOUND: " + ++count);
			for(int i = 0; i<n; i++)
			{
				for(int j = 0; j<n; j++) out.print(g[i][j]+" ");
				out.println();
			}
			return true;
		}
		return false;
	}
	if(c == n)
	{
		return go(n, r+1, 0, g);
	}
	if(r == c)
	{
		return go(n, r, c+1, g);
	}
	if(r > c)
	{
		g[r][c] = 1 - g[c][r];
		return go(n, r, c+1, g);
	}
	int rand = (c+r)%2;//new Random().nextInt(2);
	if(r == n-4 && c == n-1) rand ^= 1;
	for(int i = 1; i>=0; i--)
	{
		g[r][c] = rand;
		if(go(n, r, c+1, g)) return true;
		System.out.println(r+" "+c);
		rand ^= 1;
	}
	return false;
}
public static class input {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(reader.readLine());
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}
}