CF2023A Concatenation of Arrays

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 $ .