POLYMUL - Polynomial Multiplication


Sam and Dean fight the supernatural creatures to protect the humans. Now they have come across a creature called the Vedala, which are always found in pairs. Each vedala can be represented by a polynomial. Both the Vedalas need to be killed at once or else they can't be killed. They can be killed only by using the product of the two polynomials representing the two Vedala. Help Sam and Dean find the product of the polynomials fast, so they can do thier work. 

Input

First line contains an integer T (≤ 10), number of test cases.

Each test case will have n (n ≤ 10000), maximum degree of the polynomials on the first line. 

Next two lines will have n+1 space separated integers each representing the coeffiecients of first and second polynomials respectively.

All input coefficients values are <=1000.

Output

For each test case ouput a line of 2n space seperated integers indicating coefficients of the polynomial created after multiplication.

Example

Input:
2
2
1 2 3
3 2 1
2
1 0 1
2 1 0

Output:
3 8 14 8 3
2 1 2 1 0

Explaination

1st test case n=2, the polynomials are x^2 + 2x + 3 and 3x^2 + 2x + 1.

On multiplying we get 3x^4 + 8x^3 + 14x^2 + 8x + 3 and hence the answer is 3 8 14 8 3.

2nd test case n=2, the polynomials are x^2 + 1 and 2x^2 + x. 

On multiplying we get 2x^4 + x^3 + 2x^2 + x and hence the answer is 2 1 2 1 0. 


hide comments
ankit_mnnit: 2018-10-29 18:55:02

Use long long in place of int for coefficients it causes me 1 WA

rd10: 2018-10-21 13:42:05

Accepted with plain brute algo with O(n^2) time also.

mohinem: 2017-11-25 10:50:54

Requires FFT.

Never knew of complex data type in c++...... learnt something new :)

weramajstor: 2017-08-12 17:36:02

I'm kind of dissapointed...Before trying to write my first Karatsuba,I tested if this problem would pass with using optimised(fast input) O(n^2) algorithm in C++ and it turns out it does pass...Well atleast you can compare your Karatsuba/FFT time with your O(N^2) algorithm.Constraints should have been 10^5 and then it would be fun

Last edit: 2017-08-12 17:37:35
galloska: 2016-11-01 05:03:28

Just FYI: You have to print 2*n + 1 values.

Mateus Gonçalves de Oliveira [ITA]: 2015-10-14 04:15:57

Be careful with the limits. The coefficients might not fit in a 32bit integer.

Eddy Cael: 2015-08-17 04:57:41

Easy with fft.

prateek goyal: 2015-06-16 14:02:16

@Abhra output contain 2n integers or 2n+1 integers ??

Muhammad Rifayat Samee (Sanzee): 2015-05-30 19:55:19

getting WA....Need some test cases...
I am using FFT

mkrjn99: 2015-03-05 10:26:26

Took 3 days to get AC, but totally worth it!


Added by:Abhra
Date:2014-02-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64