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

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

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

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

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


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

hide comments
2014-11-23 12:08:02 mehmetin
32 bit signed integer is enough.

Last edit: 2012-05-29 08:43:14
2014-11-23 12:08:02 :D
64 bit signed integer will suffice.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.