The genius chess player A. Robbie gives you a puzzle on an empty ~N~ by ~N~ chessboard. To complete this puzzle, you must place at most ~\lfloor \frac{N^2 + 3N}{5} \rfloor~ knights such that every square on the chessboard contains a knight or is being attacked by a knight. Formally, a knight on square ~(x,y)~ attacks a square ~(i,j)~ if ~|x-i| = 1~ and ~|y-j|=2~, or ~|x-i| = 2~ and ~|y-j|=1~. Can you solve A. Robbie's ultimate challenge?

Constraints

~8 \le N \le 2 \times 10^3~

Subtask 1 [10%]

~N = 8~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first and only line contains the integer ~N~.

Output Specification

Output ~N~ lines where each line contains ~N~ space-separated binary values, where ~0~ represents an empty square, and ~1~ represents a knight. If there are multiple solutions, output any of them. If a solution does not exist, output ~-1~.

Sample Input

8

Sample Output

0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1
1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0

Explanation for Sample

This sample is only shown to clarify the format of the output. Note that this output is incorrect, as there are greater than ~\lfloor \frac{N^2 + 3N}{5} \rfloor~ knights on the board, although all squares are either covered by a knight or attacked by a knight.