피보나치 합

피보나치 수는 다음과 같이 정의되는 정수 수열이다: $F_0 = 1$, $F_1 = 1$, 그리고 $i \ge 2$에 대해 $F_i = F_{i-2} + F_{i-1}$이다. 이 수열의 처음 몇 항은 $1, 1, 2, 3, 5, 8, \dots$ 이다.

컴퓨터 과학자 Byteazar는 수를 피보나치 진법으로 표현하는 특이한 컴퓨터를 만들고 있다. 즉, 비트열 $(b_1, b_2, \dots, b_n)$은 수 $b_1 F_1 + b_2 F_2 + \dots + b_n F_n$을 나타낸다. (여기서 $F_0$은 사용하지 않는다는 점에 유의하라.) 안타깝게도 이 표현은 유일하지 않다. 즉, 같은 수가 여러 표현을 가질 수 있다. 예를 들어 수 $42$는 $(0,0,0,0,1,0,0,1)$, $(0,0,0,0,1,1,1,0)$, $(1,1,0,1,0,1,1)$ 로 쓸 수 있다. 이런 이유로 Byteazar는 다음 두 조건을 만족하는 표현만 사용하기로 했다.

• $n > 1$이면 $b_n = 1$이다. 즉, 표현에 앞자리 $0$이 없다.
• $b_i = 1$이면 $b_{i+1} = 0$이다 ($i = 1, \dots, n-1$). 즉, 표현에 연속한 두 개(이상)의 $1$이 없다.

Byteazar는 덧셈을 구현하는 데 어려움을 겪고 있다. 그를 도와라!

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 두 양의 정수의 표현을 읽는다.
• 그 합의 표현을 계산하여 표준 출력에 쓴다.

입력에는 위 조건을 만족하는 두 양의 정수 $x$와 $y$의 피보나치 표현이 담겨 있으며, 하나는 첫째 줄에, 다른 하나는 둘째 줄에 주어진다. 각 표현은 공백 하나로 구분된 음이 아닌 정수들의 수열이다. 줄의 첫 번째 수는 표현의 길이 $n$을 나타내며 $1 \le n \le 1\,000\,000$이다. 그 뒤에 $n$개의 $0$ 또는 $1$이 이어진다.

출력의 유일한 한 줄에, 합 $x + y$의 (위 조건을 만족하는) 피보나치 표현을 쓴다. 표현은 입력 절에서 설명한 것처럼 공백 하나로 구분된 음이 아닌 정수들의 수열이어야 한다. 줄의 첫 번째 수는 표현의 길이 $n$을 나타내며 $1 \le n \le 1\,000\,000$이고, 그 뒤에 $n$개의 $0$ 또는 $1$이 이어진다.