# [Solution] Array Recovery solution codeforces

Array Recovery solution codeforces – For an array of non-negative integers 𝑎a of size 𝑛n, we construct another array 𝑑d as follows: 𝑑1=𝑎1d1=a1𝑑𝑖=|𝑎𝑖𝑎𝑖1|di=|ai−ai−1| for 2𝑖𝑛2≤i≤n.

Table of Contents

## [Solution] Array Recovery solution codeforces

Your task is to restore the array 𝑎a from a given array 𝑑d, or to report that there are multiple possible arrays.

Input

The first line contains a single integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases.

The first line of each test case contains one integer 𝑛n (1𝑛1001≤n≤100) — the size of the arrays 𝑎a and 𝑑d.

The second line contains 𝑛n integers 𝑑1,𝑑2,,𝑑𝑛d1,d2,…,dn (0𝑑𝑖1000≤di≤100) — the elements of the array 𝑑d.

It can be shown that there always exists at least one suitable array 𝑎a under these constraints.

## [Solution] Array Recovery solution codeforces

For each test case, print the elements of the array 𝑎a, if there is only one possible array 𝑎a. Otherwise, print 1−1.

Example
input

Copy
3
4
1 0 2 5
3
2 6 3
5
0 0 0 0 0
output

## [Solution] Array Recovery solution codeforces

1 1 3 8
-1
0 0 0 0 0

Note

In the second example, there are two suitable arrays: [2,8,5][2,8,5] and [2,8,11][2,8,11].