이진법이여, 안녕?

괴짜 계산광 모임이 수를 세는 멋진 새 방법을 발견했다. 이들은 평범한 십진수 대신 피보나치 진법(Fibonacci base) 을 사용한다. 이 진법의 수는 이진수처럼 $0$과 $1$의 나열로 표현되지만, 각 자리의 가중치가 $2$의 거듭제곱이 아니라 피보나치 수열의 원소이다. 이 수열은 $F_0 = 1$, $F_1 = 2$로 시작하며, $n \ge 2$에 대해 $F_n = F_{n-1} + F_{n-2}$로 정의된다(즉 $1, 2, 3, 5, 8, \dots$).

표현에서 가장 오른쪽 자리의 가중치가 $F_0$ 이고, 왼쪽으로 갈수록 그다음 피보나치 수가 가중치가 된다. 예를 들어

$1101001_{\mathrm{Fib}} = F_0 + F_3 + F_5 + F_6 = 1 + 5 + 13 + 21 = 40$

이다.

모든 정수는 이 진법으로 표현할 수 있지만, 그 방법이 유일하지는 않다. 예를 들어 $40$은 $10001001_{\mathrm{Fib}}$로도 표현된다. 그러나 임의의 정수에 대해 $1$이 서로 이웃하지 않는 표현이 유일하게 존재하며, 이를 정규 표현(canonical representation) 이라 부른다. 예를 들어 $40$의 정규 표현은 $10001001_{\mathrm{Fib}}$이다.

피보나치 진법으로 계산하는 컴퓨터를 만들기 위해, 피보나치 진법으로 주어진 두 수(반드시 정규 표현일 필요는 없다)를 더하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 한 줄이다. 각 줄에는 피보나치 진법으로 표현된 두 수 $X$와 $Y$가 공백 하나로 구분되어 주어진다. 두 수는 각각 최대 $40$자리이다. 입력의 끝은 파일의 끝(EOF)으로만 표시되며, 별도의 표식은 없다.

각 테스트 케이스에 대해 다음 네 줄을 출력한다.

1. 첫째 줄: $X$의 정규 표현. 왼쪽을 공백으로 채워 정렬한다.
2. 둘째 줄: 더하기 기호 + 다음에 $Y$의 정규 표현. 왼쪽을 공백으로 채워 정렬한다.
3. 셋째 줄: 공백 두 칸 다음에, 합의 정규 표현과 같은 길이만큼 빼기 기호 -를 출력한다.
4. 넷째 줄: 공백 두 칸 다음에 $X + Y$의 정규 표현.

$X$, $Y$, $X + Y$의 가장 낮은 자리(가장 오른쪽 자리)가 같은 열에 오도록 $X$와 $Y$의 왼쪽을 공백으로 채운다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.