Даны целые неотрицательные числа \(n\) и \(k\). Постройте последовательность из \(n\) целых неотрицательных (т.е. \(\geq 0\)) чисел \(a_1, a_2, \ldots, a_n\) таких, что
- \(\sum\limits_{i = 1}^n a_i = k\).
- Количество \(1\) в двоичной записи числа \(a_1 | a_2 | \ldots | a_n\) максимально, где \(|\) обозначает операцию побитового ИЛИ.
Выходные данные
Для каждого набора входных данных выведите на отдельной строке последовательность \(a_1, a_2, \ldots, a_n\), удовлетворяющую приведенным выше условиям.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных нам нужно вывести ровно одно число, поэтому в качестве ответа мы можем вывести только \(5\).
Во втором наборе входных данных мы выводим \(1, 2\). Они имеют сумму \(3\), а \(1 | 2 = (11)_2\) имеет две \(1\) в двоичном представлении. Можно показать, что большего количества единиц достичь нельзя.
В четвертом наборе входных данных мы выводим \(3, 1, 1, 32, 2, 12\), что в сумме составляет \(51\), и \(3 | 1 | 1 | 32 | 2 | 12 = (101\,111)_2\) имеет пять \(1\) в двоичном представлении. Можно показать, что большего количества единиц достичь нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 5
2 3
2 5
6 51
|
5
1 2
5 0
3 1 1 32 2 12
|