A. Склеивание массивов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны $$$n$$$ массивов $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$. Длина каждого массива равна двум. Таким образом, $$$a_i = [a_{i, 1}, a_{i, 2}]$$$. Вам надо склеить массивы в один массив длины $$$2n$$$ так, чтобы количество инверсий$$$^{\dagger}$$$ в получившемся массиве было как можно меньше. Обратите внимание, что вам не нужно считать само количество инверсий.

Более формально, вам надо выбрать перестановку$$$^{\ddagger}$$$ $$$p$$$ длины $$$n$$$, чтобы массив $$$b = [a_{p_1,1}, a_{p_1,2}, a_{p_2, 1}, a_{p_2, 2}, \ldots, a_{p_n,1}, a_{p_n,2}]$$$ содержал как можно меньше инверсий.

$$$^{\dagger}$$$Количество инверсий в массиве $$$c$$$ — это количество пар индексов $$$i$$$ и $$$j$$$, таких что $$$i < j$$$ и $$$c_i > c_j$$$.

$$$^{\ddagger}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество массивов.

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$a_{i,1}$$$ и $$$a_{i,2}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — элементы $$$i$$$-го массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$2n$$$ целых чисел — элементы полученного вами массива. Если существует несколько решений, выведите любое из них.

Пример
Входные данные
4
2
1 4
2 3
3
3 2
4 3
2 1
5
5 10
2 3
9 6
4 1
8 7
1
10 20
Выходные данные
2 3 1 4
2 1 3 2 4 3
4 1 2 3 5 10 8 7 9 6
10 20
Примечание

В первом наборе входных данных мы склеили массивы в порядке $$$2, 1$$$. Рассмотрим инверсии в полученном массиве $$$b = [2, 3, 1, 4]$$$:

  • $$$i = 1$$$, $$$j = 3$$$, так как $$$b_1 = 2 > 1 = b_3$$$;
  • $$$i = 2$$$, $$$j = 3$$$, так как $$$b_2 = 3 > 1 = b_3$$$.

Таким образом, количество инверсий равно $$$2$$$. Можно доказать, что это минимально возможное количество инверсий.

Во втором наборе входных данных мы склеили массивы в порядке $$$3, 1, 2$$$. Рассмотрим инверсии в полученном массиве $$$b = [2, 1, 3, 2, 4, 3]$$$:

  • $$$i = 1$$$, $$$j = 2$$$, так как $$$b_1 = 2 > 1 = b_2$$$;
  • $$$i = 3$$$, $$$j = 4$$$, так как $$$b_3 = 3 > 2 = b_4$$$;
  • $$$i = 5$$$, $$$j = 6$$$, так как $$$b_5 = 4 > 3 = b_6$$$.

Таким образом, количество инверсий равно $$$3$$$. Можно доказать, что это минимально возможное количество инверсий.

В третьем наборе входных данных мы склеили массивы в порядке $$$4, 2, 1, 5, 3$$$.