A. Array Issue
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Caio Harley is a dedicated competitive programmer and has been studying various algorithms related to arrays. One day he was analyzing various arrays and trying to find out the solution for the following problem: what is the subarray with the largest sum?

Now, instead of executing this algorithm for the entire array, he decides to do it for every prefix of the array. More formally, for an array of $$$n$$$ integers, he executes the algorithm for every $$$i$$$ from $$$1$$$ to $$$n$$$ on the prefix $$$1 ... i$$$. However, he was too tired of running several algorithms by himself, and so he calls upon you for help! Given an array $$$a$$$ of $$$n$$$ integers, help him find out the largest subarray sum for every prefix.

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases that Caio gives to you.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the length of the array of that test case.

The second line of each test case contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-10^{11} \leq a_i \leq 10^{11})$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For the $$$i^{th}$$$ test case, output $$$n_i$$$ integers in a single line — the answer for each prefix.

Examples
Input
3
3
-1 -4 -5
4
-2 5 9 10
5
4 -4 4 -4 9
Output
0 0 0
0 5 14 24
4 4 4 4 9
Input
1
5
4 -3 0 6 1
Output
4 4 4 7 8