Concatenation of Arrays
Contest: Codeforces Round 980 (Div. 1)
Difficulty rating: 1300
Tags: constructive algorithms, greedy, math, sortings

You are given $$$n$$$ arrays $$$a_1$$$, $$$\ldots$$$, $$$a_n$$$. The length of each array is two. Thus, $$$a_i = [a_{i, 1}, a_{i, 2}]$$$. You need to concatenate the arrays into a single array of length $$$2n$$$ such that the number of inversions$$$^{\dagger}$$$ in the resulting array is minimized. Note that you do not need to count the actual number of inversions.

More formally, you need to choose a permutation$$$^{\ddagger}$$$ $$$p$$$ of length $$$n$$$, so that the array $$$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}]$$$ contains as few inversions as possible.

$$$^{\dagger}$$$The number of inversions in an array $$$c$$$ is the number of pairs of indices $$$i$$$ and $$$j$$$ such that $$$i < j$$$ and $$$c_i > c_j$$$.

$$$^{\ddagger}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of arrays.

Each of the following $$$n$$$ lines contains two integers $$$a_{i,1}$$$ and $$$a_{i,2}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — the elements of the $$$i$$$-th array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output $$$2n$$$ integers — the elements of the array you obtained. If there are multiple solutions, output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we concatenated the arrays in the order $$$2, 1$$$. Let's consider the inversions in the resulting array $$$b = [2, 3, 1, 4]$$$:

- $$$i = 1$$$, $$$j = 3$$$, since $$$b_1 = 2 > 1 = b_3$$$;
- $$$i = 2$$$, $$$j = 3$$$, since $$$b_2 = 3 > 1 = b_3$$$.

Thus, the number of inversions is $$$2$$$. It can be proven that this is the minimum possible number of inversions.

In the second test case, we concatenated the arrays in the order $$$3, 1, 2$$$. Let's consider the inversions in the resulting array $$$b = [2, 1, 3, 2, 4, 3]$$$:

- $$$i = 1$$$, $$$j = 2$$$, since $$$b_1 = 2 > 1 = b_2$$$;
- $$$i = 3$$$, $$$j = 4$$$, since $$$b_3 = 3 > 2 = b_4$$$;
- $$$i = 5$$$, $$$j = 6$$$, since $$$b_5 = 4 > 3 = b_6$$$.

Thus, the number of inversions is $$$3$$$. It can be proven that this is the minimum possible number of inversions.

In the third test case, we concatenated the arrays in the order $$$4, 2, 1, 5, 3$$$.

Example input:
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

Example output:
2 3 1 4
2 1 3 2 4 3
4 1 2 3 5 10 8 7 9 6
10 20

Editorial:
Let's sort the arrays in order of non-decreasing sum of elements. It turns out that it is always optimal to concatenate the arrays in this order.
To prove this, let's consider some optimal answer. Note that if in the final order there are two adjacent arrays, such that the sum of the elements of the left array is greater than the sum of the elements of the right array, then we can swap them, and the number of inversions will not increase. Thus, we can bring any optimal answer to ours by swapping adjacent arrays so that the number of inversions does not increase each time. Thus, such an order is truly optimal.