D :: Incredible Coding Products Company

Time Limit: 10 Seconds    Memory Limit: 65536 KB

Incredible Coding Products Company (ICPC) owns lots of coding and decoding devices. They use them to code information in a way that detecting (and sometimes correcting) errors is possible.

According to Wikipedia, The Free Encyclopedia:

“In coding theory, the BCH codes form a class of cyclic error-correcting codes that are constructed using finite fields. BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Bose and D. K. Ray-Chaudhuri. The acronym BCH comprises the initials of these inventors’ names. One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low-power electronic hardware. BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, solid-state drives and two-dimensional bar codes.”

But currently ICPC has a problem. Their Multipliers are down and they cannot multiply polynomials without them. That’s why they asked you to write a program to do that.

Given the coefficients of two polynomials find the coefficients of their multiplication.

Input

The input contains several test cases.

In the first line of input comes T (0 < T ≤ 10), the number of test cases.

Each test case starts with a line containing two integers n_a and n_b (n_a,n_b < 100000), the number of non-zero coefficients in the two polynomials respectively.

The next line contains n_a pairs of integers like (a,i) where a is the coefficient of xⁱ (and is are given in increasing order). 0 ≤ a < 100, 0 ≤ i < 100000.

The next line contains n_b pairs of integers like (b,i) where a is the coefficient of xⁱ (and is are given in increasing order). 0 ≤ b < 100, 0 ≤ i < 100000.

Output

For each test case print the coefficients of the resulting polynomial in increasing order of term-degree.

Sample Input

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

Sample Output

1 2 1
6 5 1

Submit

Source: 13th Iran Nationwide Internet Contest - UT