B. Точки и минимальное расстояние
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана последовательность целых чисел $$$a$$$ длины $$$2n$$$. Вам нужно разбить эти $$$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$$$.

В $$$i$$$-ю из следующих $$$n$$$ строк выведите два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты точки, которую нужно посетить $$$i$$$-й по счету.

Если есть несколько ответов, выведите любой из них.

Пример
Входные данные
2
2
15 1 10 5
3
10 30 20 20 30 10
Выходные данные
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$$$.