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 \lt j$$$ and $$$c_i \gt 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.

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 \gt 1 = b_3$$$;
$$$i = 2$$$, $$$j = 3$$$, since $$$b_2 = 3 \gt 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 \gt 1 = b_2$$$;
$$$i = 3$$$, $$$j = 4$$$, since $$$b_3 = 3 \gt 2 = b_4$$$;
$$$i = 5$$$, $$$j = 6$$$, since $$$b_5 = 4 \gt 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$$$.

Concatenation of Arrays

Examples