A. Concatenation of Arrays
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).
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\).
For each test case, output \(2n\) integers — the elements of the array you obtained. If there are multiple solutions, output any of them.
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\).