The great computer scientist Bajtazar has been building an extraordinary computer for over 15 years, in which numbers are represented in the Fibonacci system, meaning they are written as a sum of distinct, non-consecutive Fibonacci numbers. Formally, if we define the Fibonacci numbers starting from 1 and 2: $F_1 = 1, F_2 = 2, F_i = F_{i-1} + F_{i-2}$ for $i \geq 3$, then every positive integer $x$ is represented uniquely as a sequence of bits $(b_1, b_2, \dots, b_n)$ for some $n \geq 1$, satisfying the following conditions: $x = b_1 \cdot F_1 + b_2 \cdot F_2 + \dots + b_n \cdot F_n$; $b_i \in \{0, 1\}$ for all $1 \leq i < n$ and $b_n = 1$ (only zeros and ones, no leading zeros); * $b_i \cdot b_{i+1} = 0$ for all $1 \leq i < n$ (there are no two adjacent ones).
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$.
A long time ago, Bajtazar asked participants of the Polish Olympiad in Informatics for help in implementing the addition of numbers in the Fibonacci system. This story took place during the "Fibonacci Sums" problem from the second stage of the XII OI and was described in the Olympiad's "blue book".
This time, the matter is more difficult, and Bajtazar has been pondering it for a good few years. He decided to ask the participants of the Potyczki Algorytmiczne for advice. Help him implement multiplication!
Input
The first line of input contains the number of test cases $t$ ($1 \leq t \leq 1000$). The next $2t$ lines contain the description of the test cases.
Each test case consists of two lines. The first line contains the representation of a positive integer $x$ in the Fibonacci system – first the number $n$ denoting its length, and then $n$ bits $b_1, b_2, \dots, b_n$. The second line contains the representation of a positive integer $y$ in the same format.
The sum of the lengths of all representations from the input does not exceed $10^6$.
Output
For each test case from the input, print the product $x \cdot y$ written in the Fibonacci system in the same format as in the input – first the length $n'$, then $n'$ bits of the resulting number. Individual numbers in the lines should be separated by single spaces.
The representations from the input and output must satisfy the conditions of the problem, so in particular, the sequence of bits must end with a one and cannot contain adjacent ones.
Examples
Input 1
2 3 1 0 1 4 0 0 0 1 2 0 1 1 1
Output 1
6 0 1 0 1 0 1 2 0 1
Note 1
In the first test case, we must multiply the numbers represented by the sequences $(1, 0, 1)$ and $(0, 0, 0, 1)$. After expanding, we get: $(1 \cdot F_1 + 0 \cdot F_2 + 1 \cdot F_3) \cdot (0 \cdot F_1 + 0 \cdot F_2 + 0 \cdot F_3 + 1 \cdot F_4) = (1 + 3) \cdot (5) = 20 = F_2 + F_4 + F_6$, so the result is the sequence $(0, 1, 0, 1, 0, 1)$ of length 6.
Subtasks
There is one group of tests where each sequence from the input has only one one ($b_n = 1$). There is also another group of tests where in each test, the total number of ones in all $2t$ sequences does not exceed 2000.