# [SOLUTION] Points and Minimum Distance Solution Codeforces

B. Points and Minimum Distance
time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You are given a sequence of integers a of length 2n2�. You have to split these 2n2� 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 (x1,y1)(�1,�1) and (x2,y2)(�2,�2) is defined as |x1x2|+|y1y2||�1−�2|+|�1−�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 (1t1001≤�≤100) — the number of testcases.

The first line of each testcase contains a single integer n (2n1002≤�≤100) — the number of points to be formed.

The next line contains 2n2� integers a1,a2,,a2n�1,�2,…,�2� (0ai10000≤��≤1000) — 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 xi�� and yi�� — 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
2
2
15 1 10 5
3
10 30 20 20 30 10
output

Copy
9
10 1
15 5
20
20 20
10 30
10 30

Note

In the first testcase, for instance, you can form points (10,1)(10,1) and (15,5)(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 |1015|+|15|=5+4=9|10−15|+|1−5|=5+4=9.

In the second testcase, you can form points (20,20)(20,20)(10,30)(10,30), and (10,30)(10,30), and visit them in that exact order. Then the length of the path will be |2010|+|2030|+|1010|+|3030|=10+10+0+0=20|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])