Description

Farmer John’s farm is beautiful, with many apple trees, and apples are the cows’ favorite food on Farmer John’s farm.

One day, the idle cow Besty sat under an apple tree. She suddenly noticed that the apple trees on the farm are all binary trees! — Of course, this kind of binary tree is not a strict (full) binary tree; it may have a left subtree but no right subtree, and vice versa.

Having just learned some Computer Science, Besty wrote down, for each node in a binary tree, the number of nodes in its left subtree. For example, consider the following tree:

                3
              /  \
             1     3
            / \   / \
           0   0  1  0
                 / \
                0   0

Then, she encodes this tree by a preorder traversal. Note that the values on leaf nodes are ignored. For convenience, Besty also puts one number at the front of such an encoding: the total number of nodes in the tree. Therefore, the code for the above tree is: 9 3 1 3 1.

In this way, each code corresponds to a unique binary tree.

Besty also found that all binary trees on the farm have the same total number of nodes. Moreover, with a fixed total number of nodes, for any valid code, there exists exactly one tree on the farm that corresponds to it.

So, Besty encodes all the binary trees according to the rule above, then sorts them lexicographically by their codes.

Now, given one code, Besty wants to know which code comes immediately after it in lexicographic order.

Input Format

Input file name: next.in.

The input contains one line: a code of a binary tree. It is guaranteed that the total number of nodes does not exceed $5\times10^3$.

Output Format

Output file name: next.out.

Output one line: the code that comes immediately after the given code in lexicographic order. If the input code is the last one, output -1.

9 3 1 3 1

9 3 1 3 2 0

Hint

Translated by ChatGPT 5