Background

XCPC ONLINE is a next-generation VR virtual game. In this world, you will experience crafting iron, refining copper, molding silver, collecting gold, and might even become a legendary figure.

Today, you successfully logged into the XCPC NUAA server and received a starter pack.

Problem Statement

You have obtained a non-decreasing array $a$ of length $n$ (meaning that for all $i < j$, $a[i] \leq a[j]$) and have been granted a magical ability:

• You can choose two integers $i$ and $j$ such that $1 \leq i < j \leq n$ and perform the following operation: increase $a[i]$ by $1$ and decrease $a[j]$ by $1$.

For example, if the array $a = [1, 3, 5]$, and you choose $i = 1$ and $j = 3$ and use the magic, it becomes $a = [2, 3, 4]$.

The use of magic is restricted. The XCPC system prefers non-decreasing arrays, so after each use of the magic, the array $a$ must remain non-decreasing.

Your task is to randomly apply this operation on valid $i, j$ pairs until it is no longer possible to use the magic. Finally, print the contents of the array $a$ after all operations have been completed.

Input Format

This problem contains multiple test cases.

• The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains an integer $n$ $(1 \leq n \leq 2 \times 10^6)$, representing the length of the array $a$.
• The second line contains $n$ integers $a_i$ $(1 \leq a_i \leq 10^9)$, representing the initial values of the array.

It is guaranteed that the total sum of $n$ over all test cases does not exceed $2 \times 10^6$.

Output Format

For each test case, output $n$ integers representing the contents of the array $a$ after it is no longer possible to apply the magic.

Example

Input

1
2
1 3

Output

2 2