Вам задана последовательность целых чисел \(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\) была минимально возможной.
Выходные данные
На каждый набор входных данных в первую строку выведите минимально возможную длину пути \(s\).
В \(i\)-ю из следующих \(n\) строк выведите два целых числа \(x_i\) и \(y_i\) — координаты точки, которую нужно посетить \(i\)-й по счету.
Если есть несколько ответов, выведите любой из них.
Примечание
В первом наборе входных данных можно, например, составить точки \((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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|