The next partition into summands#603
Partitions of into summands are sets of positive integers whose sum is . Partitions that differ only by the order of summands are considered the same, so we can assume that the summands in a partition are sorted in non-decreasing order.
For example, there are partitions of into summands:
In the example, the partitions are ordered lexicographically—first by the first summand, then by the second, and so on. In this problem, you are given a partition and are asked to find the next partition in lexicographic order.
The input file contains a single line: a partition of (1 \leq n \leq 100\,000) into summands. The summands are given in non-decreasing order.
Print a single line: the partition of into summands that is next in lexicographical order after the one from the input file. If the input file contains the last possible partition of , output No solution.
Example 1