Consider a special kind of system of linear equations. To be more specific, you are given a system of N linear equations of the following form:

x2 + x3 + ... + xN - 1 + xN = a1
x1 + x3 + ... + xN - 1 + xN = a2
...
x1 + x2 + ... + xN - 2 + xN = aN - 1
x1 + x2 + ... + xN - 2 + xN - 1 = aN

In other words, i'th equation of the system consists of the sum of all the variable x1, ..., xN except xi to the left of the equality sign and the constant ai to the right of the equality sign.

One can easily prove, that a system of linear equations as described above always have exactly one solution in case N is greater than one. Your task is to find the solution of the system(such a sequence x1, x2, ..., xN, that turns each of the equations into equality). It's guaranteed, that the solution of the system is a sequence consisting only of integers from the range [1, 10^8].

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of the test case description contains one integer N denoting the number of equations in the system.

The second line contains N integers a1, a2, ..., aN denoting the constants defining a system of linear equations, that you are asked to solve.

Output

For each test case, output a single line containing N integers: a sequence x1, x2, ..., xN, which is the solution of the system.

Constraints

1 ≤ T ≤ 25000

2 ≤ N ≤ 50000

1 ≤ ai ≤ 5 × 10^12

1 ≤ xi ≤ 10^8

The sum of all N in the input is not greater than 50000