Можно показать, что любое натуральное число x единственным образом представимо в виде x = 1 + 2 + 4 + ... + 2k - 1 + r, где k и r — целые, k ≥ 0, 0 < r ≤ 2k. Такое представление будем называть степным разбиением x на слагаемые.
Например, степные разбиения чисел 12, 17, 7 и 1 выглядят так:
12 = 1 + 2 + 4 + 5,17 = 1 + 2 + 4 + 8 + 2,
7 = 1 + 2 + 4,
1 = 1.
Алиса взяла последовательность натуральных чисел (элементы в которой могли повторяться), каждый элемент последовательности заменила на последовательность из всех слагаемых его степного разбиения, расположила все получившиеся числа в неубывающем порядке и отдала Борису. Теперь Борису интересно, сколько элементов могло быть в исходной последовательности Алисы. Найдите все возможные варианты!
Выходные данные
Выведите в возрастающем порядке все возможные значения m такие, что существует последовательность натуральных чисел длины m такая, что если каждый элемент последовательности заменить слагаемыми из его степного разбиения и расположить получившиеся числа в неубывающем порядке, получится последовательность чисел, заданная во входных данных.
Если таких значений m не существует, выведите единственное число -1.
Примечание
В первом примере Алиса могла получить такую последовательность чисел из последовательности [6, 20].
Во втором примере последовательностью Алисы могла быть как [4, 5], так и [3, 3, 3].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1 1 2 2 3 4 5 8
|
2
|
|
2
|
6
1 1 1 2 2 2
|
2 3
|
|
3
|
5
1 2 4 4 4
|
-1
|