POLTOPOL - Polynomial f(x) to Polynomial h(x)

no tags 

Given polynomial of degree d, f(x)=c0+c1x+c2x2+c3x3+...+cdxd

For each polynomial f(x) there exists polynomial g(x) such that:

-> f(x)=g(x)-g(x-1) for each integer x

-> g(0)=0

Your task is to calculate polynomial h(x)=g(x)/x

(Note : degree of polynomial h(x) = degree of polynomial f(x))

Input

The first line of input contain an integer T, T is number of test cases (0<T≤104)

Each test case consist of 2 lines:

- First line of the test case contain an integer d, d is degree of polynomial f(x) (0≤d≤18)

- Next line contains d+1 integers c0,c1,...,cd, separated by space, represent the coefficient of polynomial f(x) (-231<c0,c1,...,cd<231 and cd≠0)

Output

For each test case, output the coefficient of polynomial h(x) separated by space. Each coefficient of polynomial h(x) is guaranteed to be an integer.

Example

Input:
5
0
13
1
-1 2
1
0 2
2
2 -5 9
3
23 9 21 104

Output:
13
0 1
1 1
1 2 3
31 41 59 26

---------------------------------------------------------------
Explanation for the first test case :
f(x)=13
g(x) that satisfy: g(x)-g(x-1)=f(x)=13 and g(0)=0 is: g(x)=13x
h(x)=g(x)/x so h(x)=13
output : 13
Explanation for the second test case :
f(x)=-1+2x
g(x) that satisfy: g(x)-g(x-1)=f(x)=-1+2x and g(0)=0 is: g(x)=x2
h(x)=g(x)/x so h(x)=x=0+1x
output : 0 1
Explanation for the third test case :
f(x)=0+2x
g(x) that satisfy: g(x)-g(x-1)=f(x)=2x and g(0)=0 is: g(x)=x+x2
h(x)=g(x)/x so h(x)=1+1x
output : 1 1
---------------------------------------------------------------

 

See also: Another problem added by Tjandra Satria Gunawan


hide comments
mehmetin: 2014-11-23 12:08:02

32 bit signed integer is enough.

Last edit: 2012-05-29 08:43:14
:D: 2014-11-23 12:08:02

64 bit signed integer will suffice.


Added by:Tjandra Satria Gunawan
Date:2012-05-26
Time limit:3s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem