eolymp
bolt
Try our new interface for solving problems
Məsələlər

Die Young

Die Young

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Young diagram is a well known way to describe a partition of a positive integer number. A partition of a number n is a representation as a sum of one or several integer numbers n = m_1 + m_2 + ... + m_k where m_1m_2 ≥ ... ≥ m_k.

A diagram consists of n boxes arranged in k rows, where k is the number of terms in the partition. A row representing the number m_i contains mi boxes. All rows are left-aligned, and sorted from longest to shortest.

The diagram on the picture below corresponds to the partition 10 = 5 + 3 + 2.

Sometimes it is possible to inscribe one Young diagram into the other. Diagram X can be inscribed into the diagram Y if it is possible to delete some boxes from diagram Y so that it turns to diagram X. Note that it is only allowed to remove some boxes, it is not allowed to rotate or flip the diagram. For example, the picture below shows that the diagram for 5 = 3 + 2 can be inscribed into the diagram for 10 = 5 + 3 + 2.

On the other hand, for example, it is impossible to inscribe the diagram for 8 = 4+4 into the diagram for 10 = 5 + 3 + 2.

Given n, your task to find such partition of n that the corresponding Young diagram has the greatest possible number of diagrams that can be inscribed into it.

For example, there are 36 Young diagrams that can be inscribed into the diagram for 10 = 5 + 3 + 2. However, it is not the maximal possible value. The diagram for 10 = 4 + 2 + 2 + 1 + 1 has the better value, there are 41 diagrams that can be inscribed into it.

Giriş verilənləri

Input file contains n (1n100).

Çıxış verilənləri

At the first line of the output file print the maximal number of Young diagrams that can be inscibed into some Young diagram for the partition of n.

At the second line print one or more integer numbers — the number of boxes in each row of the optimal diagram.

Nümunə

Giriş verilənləri #1
10
Çıxış verilənləri #1
41
4 2 2 1 1