Fibonacci Products

The brilliant computer scientist Bajtazar has spent more than 15 years building an unusual computer. It stores numbers in the Fibonacci system, where each number is written as a sum of distinct, non-consecutive Fibonacci numbers.

Formally, define $F_1 = 1$, $F_2 = 2$, and $F_i = F_{i-1} + F_{i-2}$ for $i \ge 3$. Every positive integer $x$ is uniquely written as a bit string $(b_1, b_2, \ldots, b_n)$ for some $n \ge 1$ that satisfies the following conditions.

• $x = b_1F_1 + b_2F_2 + \ldots + b_nF_n$
• For all $1 \le i < n$, $b_i \in \{0, 1\}$, and $b_n = 1$. There are no leading zeros.
• For all $1 \le i < n$, $b_ib_{i+1} = 0$. No two adjacent bits are both 1.

For example, $2 = (0, 1)$, $4 = (1, 0, 1)$, $5 = (0, 0, 0, 1)$, and $20 = (0, 1, 0, 1, 0, 1)$, because $20 = F_2 + F_4 + F_6 = 2 + 5 + 13$.

Long ago, Bajtazar asked Olympiad participants to help implement addition in the Fibonacci system. That story took place during the Fibonacci Sums problem from the second stage of the XII OI and is described in the Olympiad's 'blue booklet'. This time the task is harder, and Bajtazar has been stuck on it for several years. He asks Potyczki Algorytmiczne participants for advice. Help him implement multiplication!

The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The next $2t$ lines describe the test cases, two lines per case. The first line of a case gives the Fibonacci representation of a positive integer $x$: first its length $n$, then the $n$ bits $b_1, b_2, \ldots, b_n$. The second line gives the representation of $y$ in the same format. The total length of all representations in the input does not exceed $10^6$.

For each test case, print the product $x \times y$ in the Fibonacci system, in the same format as the input: first its length $n'$, then the $n'$ bits. Separate the numbers on each line with single spaces. Representations in the input and output must satisfy the conditions of the problem, so each bit string must end with a 1 and must not contain two adjacent 1s.

In the first test case, we multiply the numbers represented by $(1, 0, 1)$ and $(0, 0, 0, 1)$. Expanding gives $(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$. The result is therefore $(0, 1, 0, 1, 0, 1)$, with length 6.