F. Full Clue Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Slitherlink is a puzzle game played on a $$$n \times n$$$ grid. Some cells of the grid contain numbers (called clues). The solver must draw lines along the edges of some cells to form a loop, such that:

  • The loop does not branch off or cross itself.
  • The number written in a cell is equal to the number of edges surrounding the cell that are visited by the loop.
Example Problem
Solution

Construct a $$$n \times n$$$ slitherlink problem with full clues but multiple solutions. Moreover, there must be a pair of different solutions that satisfy all clues but share at most four edges.

Note: "full clues" means every cell in the problem should be filled with a clue number from $$$0,\ldots,4$$$. "Two solutions share $$$x$$$ edges" means that exactly $$$x$$$ edges appear in both solutions.

Input

In the first line, $$$n$$$ ($$$2\leq n \leq 20$$$). It is guaranteed that an answer always exists.

Output

First, output an $$$n \times n$$$ matrix — the problem.

Then, output two solutions — two $$$n \times n$$$ matrices. For each cell, if it is inside the loop, output "1", otherwise output "0".

Example
Input
5
Output
2 2 2 1 2
2 2 3 1 1
2 2 2 1 1
3 2 3 3 2
1 0 1 1 3

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

1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Note

The example just shows how to output the problem and solutions. It will get a Wrong Answer verdict. These two solutions share $$$9$$$ edges and the second solution doesn't satisfy all clues.