D. Константы на языке Шекспира
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Shakespeare — известный эзотерический язык, в котором программы имеют вид пьес Шекспира, а числа задаются комбинациями цветистых эпитетов. В этой задаче мы подробнее рассмотрим механизм задания чисел на этом языке.

Любая константа на Shakespeare формируется из неотрицательных степеней двойки при помощи арифметических действий. Для простоты разрешим использовать только сложение и вычитание и будем искать представление заданного числа, которое потребует минимального количества действий.

Задано натуральное число n. Надо представить его в виде n = a1 + a2 + ... + am, где каждой ai — это степень числа 2, взятая со знаком плюс или минус. Найдите такое преставление, что m — минимально.

Входные данные

Единственная строка содержит целое положительное число n, записанное в двоичной системе счисления. Длина заданного числа не превосходит 106. Гарантируется, что первая цифра числа равна 1.

Выходные данные

Выведите искомое минимальное m. Далее выведите m строк. Каждая строка должны иметь вид «+2^x» или «-2^x», где x — это показатель соответствующей степени двойки. Порядок вывода строк не имеет значения.

Примеры
Входные данные
1111
Выходные данные
2
+2^4
-2^0
Входные данные
1010011
Выходные данные
4
+2^0
+2^1
+2^4
+2^6