CF1895B.Points and Minimum Distance

You are given a sequence of integers $a$ of length $2n$. You have to split these $2n$ integers into $n$ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $a$ should become the $x$ or $y$ coordinate of exactly one point. Note that some points can be equal.

After the points are formed, you have to choose a path $s$ that starts from one of these points, ends at one of these points, and visits all $n$ points at least once.

The length of path $s$ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1-x_2| + |y_1-y_2|$.

Your task is to form $n$ points and choose a path $s$ in such a way that the length of path $s$ is minimized.

给你一个长度为 $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$ 的长度最小。

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 100$) — the number of points to be formed.

The next line contains $2n$ integers $a_1, a_2, \dots, a_{2n}$ ($0 \le a_i \le 1\,000$) — the description of the sequence $a$.

第一行包含一个整数 $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$ 的描述。

For each testcase, print the minimum possible length of path $s$ in the first line.

In the $i$-th of the following $n$ lines, print two integers $x_i$ and $y_i$ — the coordinates of the point that needs to be visited at the $i$-th position.

If there are multiple answers, print any of them.

对于每个测试用例，在第一行输出路径 $s$ 的最小可能长度。

在接下来的 $n$ 行中，第 $i$ 行输出两个整数 $x_i$ 和 $y_i$ —— 表示需要在第 $i$ 个位置访问的点的坐标。

如果存在多个答案，输出任意一个即可。

In the first testcase, for instance, you can form points $(10, 1)$ and $(15, 5)$ and start the path $s$ from the first point and end it at the second point. Then the length of the path will be $|10 - 15| + |1 - 5| = 5 + 4 = 9$.

In the second testcase, you can form points $(20, 20)$, $(10, 30)$, and $(10, 30)$, and visit them in that exact order. Then the length of the path will be $|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$.

在第一个测试用例中，例如，你可以构造点 $(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$。