Statement is not available in English language
G. Склеивание массивов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

$$$^1$$$ Количество инверсий в массиве $$$b$$$  — это количество пар индексов $$$i$$$ и $$$j$$$, таких что $$$i \lt j$$$ и $$$b_i \gt b_j$$$.

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

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

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

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

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

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

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

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