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