#P18255. Money Game 2

Money Game 2

Money Game 2

Putata 和 Budada 正在组织一个游戏。nn 名玩家围成一圈,编号为 0,1,…,n−10,1,\ldots,n-1。玩家 ii 的两名相邻玩家编号分别为 (i−1) mod n(i-1)\bmod n 和 (i+1) mod n(i+1)\bmod n。最初,玩家 ii 有整数金额 aia_i。

每轮游戏中,组织者选择一名此前没有被选择过的玩家 xx。玩家 xx 将自己当前金额的一半,向下取整,赠送给自己的一名相邻玩家。也就是说,每名玩家最多只能赠送一次;赠送前收到的钱也属于其当前金额。

令 f(i)f(i) 表示经过若干轮游戏(也可以进行零轮)后,玩家 ii 可能拥有的最大金额。请对所有 0≤i<n0\le i<n 求出 f(i)f(i)。

不同玩家的答案相互独立计算,不要求在同一组操作中同时达到所有最大值。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例包含两行:

  • 第一行包含一个整数 nn,表示玩家数;
  • 第二行包含 nn 个整数 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1},表示每名玩家的初始金额。

输出格式

对每个测试用例,输出一行 nn 个整数 f(0),f(1),…,f(n−1)f(0),f(1),\ldots,f(n-1)。

数据范围

  • 1≤T≤5×1051\le T\le5\times10^5;
  • 1≤n≤5×1051\le n\le5\times10^5;
  • 0≤ai≤1090\le a_i\le10^9;
  • 所有测试用例的 nn 之和不超过 5×1055\times10^5。

编号按模 nn 计算。因此,n=1n=1 时向相邻玩家赠送就是向自己转账,金额不变;n=2n=2 时两个方向指向同一名玩家,一轮仍只能赠送一次。

样例 1

3
5
2 1 4 3 5
5
2 1 3 1 2
1
1000000000
6 5 7 8 8
4 4 5 4 4
1000000000

样例 2

1
10
8 15 18 15 13 4 14 4 17 5
30 37 41 39 34 27 29 26 31 27