Factoradic Numbers#5547
In the factoradic number system, numbers are written similarly as in the standard decimal system, but the positions of digits have different meanings: The first (from the right) digit is always or , meaning 0 \times 1! or 1 \times 1!, respectively. The second digit may be , or , meaning 0 \times 2!, 1 \times 2! or 2 \times 2!, and so on: the digit c_i at -th position belongs to the set \{0, 1, \ldots, i\} and has value c_i \times i!.
For example, the factoradic number is 1 \times 4! + 3 \times 3! + 1 \times 2! + 0 \times 1! = 44 in decimal system. It can be easily proven that every number has a unique factoradic representation.
Given two nonnegative numbers in factoradic system, output their product in the same system. No trailing zeros are allowed, only the number zero is written simply as .
The first line contains a single integer – the number of test cases. The test cases follow.
A test case contains four lines: the first two of them describe the first factor, the last two - the other factor. Each factor is described by its length (1 \leq d \leq 2000) on the first line, and space-separated integers denoting its digits on the second line. The digits follow the format described in the statement.
For each test case, your program should write a single line containing the factoradic representation of the product - output only its digits, from left to right, space-separated.
Example 1