C. Hungry Shark
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Han hasn't eaten since 2 months ago. She had planned to eat some salmon in George's house.

George has $$$n$$$ boxes where there are $$$a_i$$$ salmons in every box $$$1 \leq i \leq n$$$.Initially,Han's score is $$$0$$$ and she starts by standing in front of box $$$1$$$.She's trying to eat all of George's salmons with the procedure as below:

  1. If she's now in front of box $$$i$$$ and there's still salmon inside the box $$$(a_i \gt 0)$$$, she will eat $$$1$$$ salmon and her score increases by $$$1$$$. The number of salmon inside the box will decrease by $$$1$$$ $$$(a_i := a_i - 1)$$$. If there's no salmon inside the box $$$(a_i = 0)$$$, she will skip this step;
  2. Move to the next box. If she's currently in front of box $$$i$$$, she will move into box $$$(i\mod n)+1$$$;
  3. Go back to step 1.

She wants to know, for each index $$$i$$$ from $$$1$$$ to $$$n$$$, what is her score as soon as there is no salmon in box $$$i$$$?

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4) $$$ — the number of test cases. Descriptions of the test cases follow.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$, the number of boxes.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the number of salmons in each box.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, print $$$n$$$ integers  — the answer for each index $$$i$$$ $$$(1 \leq i \leq n)$$$.

Example
Input
3
4
2 1 4 3
4
5 3 2 1
5
2 5 7 4 6
Output
5 2 10 9
11 9 7 4
6 19 24 17 23