Shakespeare — известный эзотерический язык, в котором программы имеют вид пьес Шекспира, а числа задаются комбинациями цветистых эпитетов. В этой задаче мы подробнее рассмотрим механизм задания чисел на этом языке.
Любая константа на Shakespeare формируется из неотрицательных степеней двойки при помощи арифметических действий. Для простоты разрешим использовать только сложение и вычитание и будем искать представление заданного числа, которое потребует минимального количества действий.
Задано натуральное число n. Надо представить его в виде n = a1 + a2 + ... + am, где каждой ai — это степень числа 2, взятая со знаком плюс или минус. Найдите такое преставление, что m — минимально.
Выходные данные
Выведите искомое минимальное m. Далее выведите m строк. Каждая строка должны иметь вид «+2^x» или «-2^x», где x — это показатель соответствующей степени двойки. Порядок вывода строк не имеет значения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1111
|
2
+2^4
-2^0
|
|
2
|
1010011
|
4
+2^0
+2^1
+2^4
+2^6
|