Дано натуральное число \(x\). Найдите любую последовательность чисел \(a_0, a_1, \ldots, a_{n-1}\) такую, что:
- \(1 \le n \le 32\),
- \(a_i\) равно \(1\), \(0\) или \(-1\) для всех \(0 \le i \le n - 1\),
- \(x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}\),
- Не существует \(0 \le i \le n - 2\) такого, что \(a_{i} \neq 0\) и \(a_{i + 1} \neq 0\).
Можно доказать, что под ограничениями задачи всегда существует как минимум одна подходящая последовательность.
Выходные данные
Для каждого набора входных данных на первой строке выведите число \(n\) (\(1 \le n \le 32\)) — длину последовательности \(a_0, a_1, \ldots, a_{n-1}\).
На следующей строке выведите саму последовательность \(a_0, a_1, \ldots, a_{n-1}\).
Если подходящих последовательностей несколько, вы можете вывести любую из них.
Примечание
В первом наборе входных данных, одной из подходящих последовательностей является \([1]\), так как \((1) \cdot 2^0 = 1\).
Во втором наборе входных данных, одной из подходящих последовательностей является \([0,-1,0,0,1]\), так как \((0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
14
24
15
27
11
19
|
1
1
5
0 -1 0 0 1
6
0 0 0 -1 0 1
5
-1 0 0 0 1
6
-1 0 -1 0 0 1
5
-1 0 -1 0 1
5
-1 0 1 0 1
|