The genius chess player A. Robbie gives you a puzzle on an empty by
chessboard. To complete this puzzle, you must place at most
knights such that every square on the chessboard contains a knight or is being attacked by a knight. Formally, a knight on square
attacks a square
if
and
, or
and
. Can you solve A. Robbie's ultimate challenge?
Constraints
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
Input Specification
The first and only line contains the integer .
Output Specification
Output lines where each line contains
space-separated binary values, where
represents an empty square, and
represents a knight. If there are multiple solutions, output any of them. If a solution does not exist, output
.
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 knights on the board, although all squares are either covered by a knight or attacked by a knight.
Comments
is the limit rounded up or down?
It is rounded down.
denotes the floor function, the greatest integer not more than
.