피보나치 곱셈

위대한 정보학자 Bajtazar는 15년 넘게 특이한 컴퓨터를 만들고 있습니다. 이 컴퓨터는 수를 피보나치 수 체계로 나타냅니다. 각 수는 서로 다르고 인접하지 않은 피보나치 수의 합으로 쓰입니다.

정의를 정확히 적으면 다음과 같습니다. $F_1 = 1$, $F_2 = 2$이고, $i \ge 3$일 때 $F_i = F_{i-1} + F_{i-2}$입니다. 모든 양의 정수 $x$는 어떤 $n \ge 1$에 대해 비트열 $(b_1, b_2, \ldots, b_n)$으로 유일하게 표현되며, 이 비트열은 다음 조건을 만족합니다.

• $x = b_1F_1 + b_2F_2 + \ldots + b_nF_n$
• 모든 $1 \le i < n$에 대해 $b_i \in \{0, 1\}$이고, $b_n = 1$입니다. 앞자리 0은 없습니다.
• 모든 $1 \le i < n$에 대해 $b_ib_{i+1} = 0$입니다. 인접한 두 1은 없습니다.

예를 들어 $2 = (0, 1)$, $4 = (1, 0, 1)$, $5 = (0, 0, 0, 1)$, $20 = (0, 1, 0, 1, 0, 1)$입니다. $20$은 $F_2 + F_4 + F_6 = 2 + 5 + 13$이기 때문입니다.

오래전 Bajtazar는 올림피아드 참가자들에게 피보나치 수 체계에서 덧셈을 구현하는 일을 도와 달라고 부탁했습니다. 이 이야기는 XII OI 2단계 '피보나치 합' 문제와 함께 올림피아드의 '파란 책'에 실렸습니다. 이번 문제는 더 어렵고, Bajtazar는 여러 해째 이 문제를 붙잡고 있습니다. 그래서 Potyczki Algorytmiczne 참가자들에게 조언을 구합니다. 곱셈을 구현하는 일을 도와주세요!

첫 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 1000$)가 주어집니다. 이어서 $2t$개의 줄에 테스트 케이스가 한 개씩 두 줄로 주어집니다. 각 케이스의 첫 줄에는 양의 정수 $x$의 피보나치 수 체계 표현이 주어집니다. 먼저 길이 $n$이 나오고, 그다음 $n$개의 비트 $b_1, b_2, \ldots, b_n$이 나옵니다. 둘째 줄에는 같은 형식으로 $y$의 표현이 주어집니다. 입력에 있는 모든 표현의 길이 합은 $10^6$을 넘지 않습니다.

각 테스트 케이스마다 곱 $x \times y$를 입력과 같은 형식으로 출력합니다. 먼저 길이 $n'$을, 그다음 $n'$개의 비트를 씁니다. 수들은 공백 한 칸으로 구분합니다. 입력과 출력의 표현은 문제의 조건을 만족해야 하므로, 비트열은 반드시 1로 끝나고 인접한 1이 없어야 합니다.

첫 번째 테스트 케이스에서는 $(1, 0, 1)$과 $(0, 0, 0, 1)$로 표현된 수를 곱합니다. 전개하면 $(1F_1 + 0F_2 + 1F_3) \times (0F_1 + 0F_2 + 0F_3 + 1F_4) = (1 + 3) \times 5 = 20 = F_2 + F_4 + F_6$입니다. 따라서 결과는 길이 6의 $(0, 1, 0, 1, 0, 1)$입니다.