赛时提醒：long long 的数值范围大于 int。在本题中，请考虑使用 long long 替代 int。

题目背景

XCPC ONLINE 是一款次世代 VR 虚拟游戏。在这个世界里，你将经历打铁、炼铜、首银、摄金，甚至有望成为一代传奇。

今天，你成功登录到 XCPC NUAA 服务器，并领取了新手礼包。

题目描述

你获得了一个长度为 $n$ 的不减数组 $a$（即满足 $\forall i < j, a[i] \leq a[j]$），并被赋予了一种神奇的魔法：

• 你可以选择两个满足 $1 \leq i < j \leq n$ 的正整数 $i$ 和 $j$，然后执行以下操作：将 $a[i]$ 增加 $1$，将 $a[j]$ 减少 $1$。

例如，对于数组 $a = [1, 3, 5]$，若选择 $i = 1$ 和 $j = 3$ 并使用魔法，则变为 $a = [2, 3, 4]$。

魔法的使用受到限制。XCPC 系统偏好单调不减的数组，因此在每次使用魔法后，你必须保证数组 $a$ 仍然是单调不减的。

你的任务是：每次随机选择符合条件的 $i, j$ 进行操作，直到无法再施展魔法为止。最终，打印所有操作结束后数组 $a$ 的内容。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试用例的数量。

对于每组测试数据：

• 第一行包含一个整数 $n$ ($1 \leq n \leq 2 \times 10^6$)，表示数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_i$ ($1 \leq a_i \leq 10^9$)，表示数组的初始值。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每组数据，输出 $n$ 个整数，表示无法再施展魔法时数组 $a$ 的内容。

样例 #1

样例输入 #1

1
2
1 3

样例输出 #1

2 2