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