给你一个长度为$$$2n$$$的整数序列$$$a$$$。您必须将这些 $$$2n$$$ 整数拆分为 $$$n$$$ 对;每对将代表平面上一个点的坐标。序列 $$$a$$$ 中的每个数字都应该恰好成为一个点的 $$$x$$$ 或 $$$y$$$ 坐标。请注意,某些点可以相等。
点形成后,你必须选择一条路径$$$s$$$,从这些点之一开始,到这些点之一结束,并至少访问所有$$$n$$$点一次。
路径 $$$s$$$ 的长度是路径上所有相邻点之间的距离之和。在此问题中,两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的距离定义为 $$$|x_1-x_2| + |y_1-y_2|$$$。
你的任务是形成$$$n$$$点并选择一条路径$$$s$$$,使得路径$$$s$$$的长度最小化。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 要形成的点数。
下一行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$ ($$$0 \le a_i \le 1\,000$$$) - 序列 $$$a$$$ 的描述。
输出
对于每个测试用例,在第一行中打印路径 $$$s$$$ 的最小可能长度。
在接下来的 $$$n$$$ 行的第 $$$i$$$ 行中,打印两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 位置需要访问的点的坐标。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
2 2 15 1 10 5 3 10 30 20 20 30 10
输出 #1
9 10 1 15 5 20 20 20 10 30 10 30
注意
例如,在第一个测试用例中,您可以形成点 $$$(10, 1)$$$ 和 $$$(15, 5)$$$ 并从第一个点开始路径 $$$s$$$ 并在第二个点结束。那么路径的长度将为$$$|10 - 15| + |1 - 5| = 5 + 4 = 9$$$。
在第二个测试用例中,您可以形成点 $$$(20, 20)$$$、$$$(10, 30)$$$ 和 $$$(10, 30)$$$,并按照确切的顺序访问它们。那么路径的长度将为$$$|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$$$。