[SOLUTION] Points and Minimum Distance Solution Codeforces

You are given a sequence of integers $a$ of length $2 n$ . You have to split these $2 n$ 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.

Input

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

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

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

Output

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.

Example

input

Copy

15 1 10 5

10 30 20 20 30 10

output

Copy

Note

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$ .

SOLUTION

# Function to calculate the minimum possible length of the path and the points to visit
def minimum_path_length(n, a):
a.sort()
min_length = 0
points = []

for i in range(n):
x = a[i]
y = a[i + n]
min_length += (x – a[0]) + (a[n] – x)
points.append((x, a[0]))
points.append((x, a[n]))

return min_length, points

# Read the number of test cases
t = int(input())

# Iterate through each test case
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
min_length, points = minimum_path_length(n, a)
print(min_length)
for point in points:
print(point[0], point[1])

Leave a Comment Cancel reply