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 .