Problem: Before the start of the football season in Berland a strange magic ritual is held. The most experienced magicians have to find a magic matrix of the size n × n (n is even number). Gods will never allow to start the championship without it. Matrix should contain integers from 0 to n - 1, main diagonal should contain only zeroes and matrix should be symmetric. Moreover, all numbers in each row should be different. Magicians are very tired of the thinking process, so they ask you to write a program to find such matrix.

Input

The first line contains one integer n (2 ≤ n ≤ 1000), n is even.

Output

Output n lines with n numbers each — the required matrix. Separate numbers with spaces. If there are several solutions, output any.

Examples

Input

2


Output

0 1
1 0


Input

4


Output

0 1 3 2
1 0 2 3
3 2 0 1
2 3 1 0

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main implements Runnable  {
	public void solution() throws IOException {
		int n = in.nextInt();
		int[][] a = new int[n][n];
		boolean[][] r = new boolean[n][n];
		boolean[][] c = new boolean[n][n];
		for (int i = 0; i < n; ++i) {
			r[i][0] = true;
			c[i][0] = true;
		}
		for (int i = 0; i < a.length; ++i) {
			int cur = i;
			for (int j = 0; j < n; ++j) {
				if (i == j) {
					if (j + 1 < n) {
						cur = next(i, j + 1, cur, r, c);
					}
				} else {
					a[i][j] = cur;
					r[i][cur] = true;
					c[j][cur] = true;
					if (j + 1 < n) {
						cur = next(i, j + 1, cur, r, c);
					}
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (j != 0) {
					out.print(' ');
				}
				out.print(a[i][j]);
			}
			out.println();
		}
	}

	private int next(int i, int j, int cur, boolean[][] r, boolean[][] c) {
		j %= r.length;
		cur = (cur + 1) % r.length;
		for (int k = 0; k < 2 * r.length; ++k) {
			if (r[i][cur] || c[j][cur]) {
				cur = (cur + 1) % r.length;
			} else {
				break;
			}
		}
		return cur;
	}

	public void run() {
		try {
			solution();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public static void main(String[] args) throws IOException {
		new Thread(null, new Main(), "", 1 << 28).start();
	}
	
	private class Scanner {
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		public Scanner(BufferedReader reader) {
			this.reader = reader;
			this.tokenizer = new StringTokenizer("");
		}
		
		public boolean hasNext() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				String next = reader.readLine();
				if (next == null) {
					return false;
				}
				tokenizer = new StringTokenizer(next);
			}
			return true;
		}
		
		public String next() throws IOException {
			hasNext();
			return tokenizer.nextToken();
		}
		
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
	}
	
	Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}