Феникс решил стать ученым! Сейчас он изучает рост бактерий.
Изначально, в день \(1\), есть одна бактерия массой \(1\).
Каждый день некоторое количество бактерий делятся (возможно, все или ни одной). Когда бактерия массой \(m\) делится, она превращается в две бактерии массой \(\frac{m}{2}\) каждая. Например, бактерия массой \(3\) может разделиться на две бактерии массой \(1.5\).
Каждую ночь масса каждой бактерии увеличивается на один.
Феникса интересует вопрос: может ли общая масса бактерий стать в точности равна \(n\). Если может, то его интересует как добиться такой массы за минимальное количество ночей. Помогите ему стать самым лучшим ученым!
Выходные данные
Для каждого набора входных данных, если не существует способа получить общую массу равную \(n\), выведите -1. В противном случае, выведите две строки.
В первой строке выведите целое число \(d\) — минимальное необходимое количество ночей.
В следующей строке выведите \(d\) целых чисел, где \(i\)-е число обозначает количество бактерий, которые поделятся в \(i\)-й день.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе, можно получить общую массу бактерий ровно \(9\) следующим образом:
- День \(1\): Бактерия с массой \(1\) делится. Получаем две бактерии с массой \(0.5\).
- Ночь \(1\): Все бактерии увеличивают массу на один. Получаем две бактерии с массой \(1.5\).
- День \(2\): Ни одна бактерия не делится.
- Ночь \(2\): Получаем две бактерии с массой \(2.5\).
- День \(3\): Обе бактерии делятся. Получаем четыре бактерии с массой \(1.25\).
- Ночь \(3\): Получаем четыре бактерии с массой \(2.25\).
Суммарная масса равна
\(2.25+2.25+2.25+2.25=9\). Можно доказать, что
\(3\) — минимальное необходимое количество ночей. Есть и другие способы добиться суммарной массы 9 за 3 ночи.
\( \)
В втором наборе, можно получить общую массу бактерий ровно \(11\) следующим образом:
- День \(1\): Бактерия с массой \(1\) делится. Получаем две бактерии с массой \(0.5\).
- Ночь \(1\): Получаем две бактерии с массой \(1.5\).
- День \(2\): Одна бактерия делится. Получаем три бактерии с массами \(0.75\), \(0.75\) и \(1.5\).
- Ночь \(2\): Получаем три бактерии с массами \(1.75\), \(1.75\) и \(2.5\).
- День \(3\): Бактерия с массой \(1.75\) и бактерия с массой \(2.5\) делятся. Получаем пять бактерий с массами \(0.875\), \(0.875\), \(1.25\), \(1.25\) и \(1.75\).
- Ночь \(3\): Получаем пять бактерий с массами \(1.875\), \(1.875\), \(2.25\), \(2.25\) и \(2.75\).
Суммарная масса равна
\(1.875+1.875+2.25+2.25+2.75=11\). Можно доказать, что
\(3\) — минимальное необходимое количество ночей. Есть и другие способы добиться суммарной массы 11 за 3 ночи.
\( \)
Во третьем наборе, бактерия не делится в день \(1\), а потом увеличивает массу до \(2\) в ночь \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
9
11
2
|
3
1 0 2
3
1 1 2
1
0
|