描述

“荒谬计算狂热者” 小组发现了一种全新的计数方法。他们不使用常见的十进制数，而是采用斐波那契基数来表示数字。在这种基数下，数字像二进制数一样用由 0 和 1 组成的序列来表示，但在这种表示中，数位（比特？）的权重不是 2 的幂次方，而是斐波那契数列（1, 2, 3, 5, 8, … 该数列定义为$F_0$=1，$F_1$=2，且对于$n \geq 2$有递归关系$F_n$=$F_{n-1}$+$F_{n-2}$）的元素。

例如，1101001_Fib=$F_0$+$F_3$+$F_5$+$F_6$=1+5+13+21=40。

你可能会注意到，每个整数都可以用这种基数表示，但不一定是唯一的表示方式 —— 例如，40 也可以表示为10001001_Fib。 然而，对于任何整数，都存在一种不包含两个相邻 1 的唯一表示形式，我们称这种表示为规范表示。例如，10001001_Fib就是 40 的规范斐波那契表示形式。 为了证明这种数字表示方法优于其他方法，“荒谬计算狂热者” 小组（ACM）决定制造一台能够在斐波那契基数下进行计算的计算机。你的任务是编写一个程序，接受两个斐波那契基数表示的数字（不一定是规范表示形式）并将它们相加。

输入

输入由若干个实例组成，每个实例占一行。输入的每一行包含两个用单个空格分隔的斐波那契基数表示的数字$X$和$Y$。每个数字最多有 40 位。输入的结束没有特殊的标记。

输出

每个实例的输出格式如下： 第一行包含规范表示形式的数字$X$，可能在左边用空格填充。第二行以加号开头，后面跟着规范表示形式的数字$Y$，同样可能在左边用空格填充。第三行以两个空格开头，后面跟着一串长度与$X+Y$的结果长度相同的减号。第四行以两个空格开头，紧接着是$X+Y$的规范表示形式。$X$和$Y$都在左边用空格填充，使得$X$、$Y$和$X+Y$的最低有效位在输出中处于同一列。每个实例的输出后面都跟一个空行。 输入数据 1

11101 1101

1 1

输出数据 1

100101

10001

1001000

1

1

10

来源

2004 年 CTU 公开赛