Description

There is a row of $N$ coins on the table, all initially heads up. You need to turn all coins to tails up. The rule is that each time you may flip any $N-1$ coins (a heads-up coin becomes tails up, and vice versa). Find a shortest sequence of operations (each flip of $N-1$ coins counts as one operation).

Input Format

A natural number $N$ (where $N$ is an even number no greater than 100).

Output Format

The first line contains an integer $S$, the minimal number of operations needed.

The next $S$ lines each describe the state of the coins on the table after that operation (a line with $N$ integers 0 or 1, indicating each coin’s state; 0 means heads up, 1 means tails up). No extra spaces are allowed.

If there are multiple valid operation sequences, output one whose sequence of operations is lexicographically smallest.

The lexicographical order of an operation is defined as follows: for each position in a single operation, 1 means flip, and 0 means do not flip.

However, you must output the state after each operation, where 0 means heads up and 1 means tails up.

4

4
0111
1100
0001
1111

Hint

Translated by ChatGPT 5