It can be shown that any positive integer x can be uniquely represented as x=1+2+4+...+2k-1+r, where k and r are integers, k≥0, 0<r≤2k. Let's call that representation prairie partition of x.
For example, the prairie partitions of 12, 17, 7 and 1 are:
12=1+2+4+5,
17=1+2+4+8+2,
7=1+2+4,
1=1.
Alice took a sequence of positive integers (possibly with repeating elements), replaced every element with the sequence of summands in its prairie partition, arranged the resulting numbers in non-decreasing order and gave them to Borys. Now Borys wonders how many elements Alice's original sequence could contain. Find all possible options!
Output
Output,
in increasing order, all possible values of
m such that there exists a sequence of positive integers of length
m such that if you replace every element with the summands in its prairie partition and arrange the resulting numbers in non-decreasing order, you will get the sequence given in the input.
If there are no such values of
m, output a single integer
-1.
Note
In the first example, Alice could get the input sequence from
[6,20] as the original sequence.
In the second example, Alice's original sequence could be either
[4,5] or
[3,3,3].