Given an integer n, you need to construct a n×n matrix M of zeroes and ones such that for every m, 1 ≤ m ≤ n, a, 1 ≤ a ≤ n-m+1 the sub-matrix formed by rows 1 through m and columns a through a+m-1 of M is non-singular over F_2.
Let us remind you that a m×m matrix P over F_2 is non-singular when there’s an odd number of permutations p of 1, 2, ..., m such that elements P_{1, p1}, P_{2, p2}, ..., P_{m, pm} are all equal to one.
The first and only line of the input file contains an integer n, 1 ≤ n ≤ 100.
Output the required matrix in n lines of n integers (zeroes or ones) each, separated with single spaces inside a line.