B. RecoveriT
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an integer $$$n$$$ and an array of $$$n$$$ elements $$$a_1,a_2...,a_n$$$.

You need to find an array $$$t$$$ of $$$n$$$ elements $$$t_1,t_2...,t_n$$$ such that the following conditions hold :

1 - $$$a_i = t_i + t_{i+1}$$$ $$$\forall i \in [1,n-1] $$$

2 - $$$a_n = t_n + t_1$$$

3 - $$$t[i] \geq 0$$$ $$$\forall i \in [1,n] $$$

Input

The first line contains an integer $$$t$$$ $$$( 1\leq t\leq 10^5)$$$, the number of test cases.

The first line of each test case contains the integer $$$n$$$ $$$( 2\leq n\leq 10^6)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$( 0\leq a_i\leq 10^{9})$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3\times10^6$$$

Output

If there doesn't exist such an array $$$t$$$ print $$$-1$$$ and return.

If there is exactly $$$one$$$ array $$$t$$$ satisfying the conditions print $$$t_1,t_2,...,t_n$$$ and return.

If there are $$$many$$$ arrays satisfying the conditions just print how many are there and return.

(One can prove that the number of such arrays is $$$fini$$$).

Scoring
  1. (10 points) $$$ 2\leq n\leq 10^3$$$ and $$$ 0\leq a_i\leq 10^3$$$.
  2. (10 points) $$$ 2\leq n\leq 10^6$$$ and $$$n$$$ is odd.
  3. (15 points) $$$ 2\leq n\leq 10^2$$$.
  4. (65 points) No additional constraints.
Example
Input
2
5
3 5 7 9 6
2
5 5
Output
1 2 3 4 5 
6
Note

- Note that in the first testcase, it's easy to prove that there is one unique array $$$t$$$ which is $$${1,2,3,4,5}$$$, since :

$$$t[1]+t[2]=a[1]=3$$$

$$$t[2]+t[3]=a[2]=5$$$

$$$t[3]+t[4]=a[3]=7$$$

$$$t[4]+t[5]=a[4]=9$$$

$$$t[5]+t[1]=a[5]=6$$$

- In the second testcase, the arrays are : $$$\{0,5\},\{1,4\},\{2,3\},\{3,2\},\{4,1\},\{5,0\}.$$$