莎士比亚是一种广为人知的深奥编程语言,其中的程序看起来像莎士比亚的戏剧,并且数字由华丽的绰号组合给出。在本题中,我们将仔细研究莎士比亚中描述数字的方式。
莎士比亚中的每个常数都是使用算术运算从 2 的非负幂创建的。为简单起见,我们只允许加法和减法,并将寻找需要最少运算次数的给定数字的表示形式。
给定一个整数 n。您必须将其表示为 n = a1 + a2 + ... + am,其中每个 ai 都是 2 的非负幂,可能乘以 -1。找到最小化 m 值的表示。
输入
输入的唯一一行包含一个正整数 n,以二进制表示法表示。符号的长度最多为106。符号的第一位数字保证为1。
输出
输出所需的最小m。之后输出m行。每行的格式必须为“+2^x”或“-2^x”,其中 x 是相应项的幂系数。行的顺序并不重要。
示例
输入 #1
1111
输出 #1
2 +2^4 -2^0
输入 #2
1010011
输出 #2
4 +2^0 +2^1 +2^4 +2^6