A. Concatenation of Arrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

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

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
Output
2 3 1 4
2 1 3 2 4 3
4 1 2 3 5 10 8 7 9 6
10 20
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$$$.