Description

Piggy Hanke especially likes eating roast chicken (we are both livestock—why cook each other so ruthlessly!). Hanke eats chicken in a special way. Why special? Because he has $10$ seasonings (mustard, cumin, etc.), and for each seasoning he can use $1$ to $3$ grams. The deliciousness of any roast chicken equals the sum of the masses of all seasonings.

Now Hanke wants to know: given a deliciousness $n$, please output all combinations of these $10$ seasonings.

Input Format

A positive integer $n$, representing the deliciousness.

Output Format

• On the first line, output the total number of solutions.
• From the second line to the end, output $10$ numbers per line, representing the mass used for each seasoning, in lexicographical order.
• If there is no valid method, output only a single $0$ on the first line.

11

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1 

Hint

For $100\%$ of the testdata, $n \leq 5000$.

Translated by ChatGPT 5