题目类型说明

这是一道提交函数题。原题要求你实现函数：

std::vector<int> solve(std::vector<int> A);

其中 A[i] 表示第 i 包糖果中的糖果数量。函数需要返回一个 0..N-1 的排列，表示 Deni 选择的取包顺序。

原题中的 solve 会在一个测试点内被调用多次；下文也给出本地评测器输入输出格式，便于改造成标准输入输出题。

---

题目描述

Martina 买了 N 包糖果，第 i 包中有 A_i 颗糖。设糖果总数为：

$$S=A_0+A_1+\cdots+A_{N-1}$$

现在 Martina 和她的妹妹 Deni 要把这些糖果分掉。她们不仅在意糖果数量，也在意拿到多少包。

她们约定如下分配流程：

1. Deni 先任意决定一个排列 i_0, i_1, ..., i_{N-1}，即糖果包的领取顺序；
2. Martina 按照这个顺序把糖果包一个个给 Deni；
3. 一旦 Deni 已经拿到的糖果总数第一次达到或超过 S/2，发放立刻停止；
4. 剩余的糖果包全部归 Martina。

Deni 很在意姐妹俩拿到的包数差，她希望最小化：

$$\left|\text{Deni 拿到的包数} - \text{Martina 拿到的包数}\right|$$

请你输出一个排列，使得上述绝对值最小。如果有多种最优解，输出任意一种即可。

---

约束条件

• 1 <= N <= 2 × 10^6
• 1 <= ΣN <= 10^7，其中 ΣN 表示同一测试文件内所有场景的 N 之和
• 1 <= T <= 5 × 10^3，其中 T 表示场景数
• 1 <= A_i <= 10^9

---

子任务

子任务	分值	依赖子任务	N	ΣN	额外限制
0		-	-		样例
1	3		<= 10^5		所有值 A_0, A_1, ..., A_{N-1} 都出现偶数次；且 A_i <= 3 × 10^7；且 T = 1
2			<= 25	<= 250	A_i = 2^i
3		2	<= 10^6	<= 5 × 10^6	A_i = 2^{s_i}，其中 0 <= s_i <= 25
4	5	-	<= 2 × 10^6	<= 10^7	A_i = i+1
5	4		<= 7	<= 3.5 × 10^4	无
6		0	<= 20	<= 200
7	19	0,2,6	<= 2 × 10^3	<= 10^4
8	28	0-2,5-7	<= 10^5	<= 5 × 10^5
9	29	0-7	<= 2 × 10^6	<= 10^7

只有当该子任务及其依赖子任务全部通过时，才能获得该子任务的分数。

---

本地评测器

输入格式

• 第 1 行：一个正整数 T，表示场景数；
• 对于每个场景：
  • 第 1 行：一个正整数 N；
  • 第 2 行：N 个整数 A_0 A_1 ... A_{N-1}。

输出格式

对于每个场景输出一行，包含 solve 返回的排列。

---

样例

输入

2
9
5 6 6 3 1 1 4 4 3
8
2 2 3 2 3 2 2 3

输出

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

样例说明

样例第一组的输出并不是唯一答案。

按照输出排列后，糖果包中的糖果数顺序为：

5, 3, 4, 4, 1, 3, 6, 6, 1

Deni 会依次拿走编号为 0, 3, 6, 7, 4 的包，总共得到：

$$5+3+4+4+1=17$$

注意前四包糖果总数为：

$$5+3+4+4=16<\frac{S}{2}=16.5$$

因此 Martina 不能更早停止，Deni 必须再拿一包。此时两人拿到的包数分别为 5 和 4，差值为：

$$|5-4|=1$$

可以证明这是最优的。