Description

There is a circle. After an integer $n\ (1≤n≤8)$ is given, it is divided into $n$ sectors. Please choose a positive integer for each sector.

After placing the numbers, you may pick a single number from one sector, or pick one number from each of two or more adjacent sectors; summing them produces a new number. Use the integers obtained in this way to form a consecutive integer sequence: $1,2,3,\cdots,i$, and make $i$ as large as possible.

Input Format

One line containing an integer $n\ (1\le n \le 8)$.

Output Format

The first line contains the maximum $i$. The following lines list all fillings that achieve this maximum $i$.

Because a circle has no inherent order, the same filling may correspond to multiple outputs. To reduce this, it is required to list the numbers starting from $1$ (since the consecutive sequence must contain $1$, the filled numbers must include $1$).

1

1
1

Hint

Translated by ChatGPT 5