specialist之路

题目描述

gq 在 Codeforces 上奋斗了许久，终于来到了关键时刻：只要再做出一道题，gq 的 rating 就将从 Pupil（绿色） 挺进 Specialist（青色）。

为了保险起见，gq 和团队一起准备了一个复杂的构造题，用于训练gq的思维能力。团队花了数小时推理，最终构造出一个满足特殊性质的整数序列：

$a_1, a_2, \dots, a_{2n+1}$.

这个序列有以下重要特性：

1. 所有数字互不相同，且值域极大：$1 \le a_i \le 10^{18}$.
2. 总共有奇数个元素 $2n+1$ 个。
3. 满足一个奇怪的“交替求和公式”：$a_1 = \sum_{i=1}^{n} (a_{2i} - a_{2i+1})$。

gq 研究了半天，终于理解了构造的关键思想——这正是让他晋级的最后训练。然而，gq 还没等写下最终答案，就接到了一个噩耗：

gq 的队友为了争抢荣誉，提前偷走了 gq 的构造，并故意破坏了它！🤬

他们从原序列中 删掉了一个元素，然后将剩下的所有数字 打乱顺序，最后把损坏的版本摆在桌上，挑战 gq：

-“既然你要当 Specialist，这点小事应该难不倒你吧？” -😓

桌上的序列是：$b_1, b_2, \dots, b_{2n}$

这是原序列删掉一个元素、再任意打乱顺序的产物。gq 现在完全不记得原来的排列，也不知道被删的是哪个数，但 gq 知道：

• 原序列一定存在，并且满足题目所有性质
• 只需要恢复 任意一个合法的原序列 即可
• 这将是 gq 成为 Specialist 的最终试炼

你能帮助 gq 在 rating 更新前完成复原吗？

形式化的，给定一个长度为 $2n$ 的整数序列 $b$，它是一个长度为 $2n+1$ 的整数序列 $a$ 删除一个元素并打乱顺序后的结果。已知 $a$ 满足：

1. 所有元素互不相同，且 $1 \le a_i \le 10^{18}$.
2. $a$ 的长度为 $2n+1$
3. 满足交替和公式：$a_1 = \sum_{i=1}^{n} (a_{2i} - a_{2i+1})$

你需要在 $b$ 的基础上，构造出任意一个合法的序列 $a$。

输入格式

输入包含多个测试用例。

• 第一行一个整数 $t（1 \le t \le 10^4）$，表示测试用例数量。

• 对每个测试用例：

  • 第一行一个整数 $n（1 \le n \le 2 \cdot 10^5）$
  • 第二行包含 $2n$ 个互不相同的整数 $b_1, b_2, \dots, b_{2n}(1 \le b_i \le 10^{9})$，表示被破坏后的序列。

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

输出格式

对每个测试用例，输出一个长度为 $2n+1$ 的互不相同整数序列 $a$，满足：

1. 原题所述交替和公式成立；
2. 从该序列删去恰好一个元素并打乱后，可得到输入的序列 $b$；
3. 所有元素在区间 $[1, 10^{18}]$ 内。 如有多个合法答案，输出任意一个。

样例 1

4
1
9 2
2
8 6 1 4
3
99 2 86 33 14 77
2
1 6 3 2

7 9 2
1 8 4 6 9
86 99 2 77 69 14 33
4 6 1 2 3