Description

Define the Fibonacci sequence as $F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}(i\ge 3)$.

For any positive integer $x$, we can always write $x$ in a unique Fibonacci representation $(b_1,b_2,...,b_n)$ that satisfies:

1. $b_1\times F_1+b_2\times F_2+...+b_n\times F_n=x$.
2. For any $i(1\le i<n)$, we have $b_i=0$ or $b_i=1$; and for $b_n$, we have $b_n=1$.
3. For any $i(1\le i<n)$, we have $b_i\times b_{i+1}=0$.

For example, $2=(0,1)$, $4=(1,0,1)$, $5=(0,0,0,1)$, $20=(0,1,0,1,0,1)=F[2]+F[4]+F[6]=2+5+13$.

Given two positive integers $A$ and $B$ in Fibonacci representation, output the Fibonacci representation of $A\times B$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

Each test case contains two lines, describing the Fibonacci representations of $A$ and $B$. Each line starts with a positive integer $n$, followed by $n$ non-negative integers $b_1,b_2,...,b_n$.

Output Format

For each test case, output one line. Follow the input format to output the Fibonacci representation of $A\times B$.

2
3 1 0 1
4 0 0 0 1
2 0 1
1 1

6 0 1 0 1 0 1
2 0 1

Hint

For $100\%$ of the testdata, $1\le T\le 10^3$, and the input guarantees that the sum of all $n$ does not exceed $10^6$.

Translated by ChatGPT 5