There are $n$ cyan points $C_1, \dots, C_n$ and $n$ blue points $B_1, B_2, \dots, B_n$ on a plane. Your task is to:

1. Find a position to place a white point $W$.
2. Pair the white point, cyan points, and blue points into $n$ triangles such that each cyan point and each blue point is in exactly one triangle.
   • We assume that for each $1 \leq i \leq n$, the corresponding triangle is $\triangle WC_iB_{p_i}$, where $p$ can be viewed as a permutation of $1 \sim n$.
3. $\angle C_iWB_{p_i}$ cannot be an acute angle. That is, $\angle C_iWB_{p_i} \geq \pi/2$.

Construct any valid solution. It can be proven that a solution always exists.

Input

Each test case contains multiple test sets.

The first line of the input contains an integer $T$, representing the number of test sets. For each test set:

The first line contains an integer $n$.

The next $n$ lines each contain two integers $x$ and $y$, describing the coordinates of point $C_i$.

The next $n$ lines each contain two integers $x$ and $y$, describing the coordinates of point $B_i$.

The input data guarantees that all given $2n$ points are distinct.

Output

For each test set:

The first line contains two real numbers $x_W, y_W$, representing the coordinates of the point $W$ you constructed. You must ensure $-10^9 \leq x_W, y_W \leq 10^9$.

The next line contains $n$ integers $p_1, p_2, \dots, p_n$, representing the permutation $p$ you constructed.

If there are multiple valid solutions, you may output any one of them.

Examples

Input 1

1
6
-6 10
-9 7
-7 -7
6 6
3 -6
2 -7
8 10
7 7
9 7
-9 9
5 5
-1 1

Output 1

-1.230077554196 2.883883476483
3 5 1 6 4 2

Note

First, in this problem, we allow points to coincide. That is, although the given $2n$ points are distinct, we allow the point $W$ you construct to be at the same position as any of the given points.

For $\angle C_iWB_{p_i}$, if $C_i = W$ or $B_{p_i} = W$, we consider the angle to be a straight angle of exactly $180$ degrees.

To avoid potential floating-point errors, we will check if your output is valid using the following method:

• Let $\varepsilon = 10^{-6}$
• For each $1 \leq i \leq n$:
  • Let $r = |C_iW|^2 + |B_{p_i}W|^2$ and $d = |C_iB_{p_i}|^2$
  • We will check if $r \leq \max(d + \varepsilon, d \cdot (1 + \varepsilon))$ holds. That is, whether $r \leq d$ holds within an absolute or relative error of at most $10^{-6}$.

Subtasks

For all data, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, $1 \leq \sum n \leq 2 \times 10^5$, and $-10^6 \leq x,y \leq 10^6$.

Please note that the subtask constraints do not include a constraint on $\sum n$. In all subtasks, there may be test cases where $\sum n$ reaches the $2 \times 10^5$ level.

Subtask 1 (6 points)

$n = 1$

Subtask 2 (8 points)

$n \leq 2$

Subtask 3 (8 points)

$n \leq 3$

Subtask 4 (14 points)

$n \leq 16$

Subtask 5 (25 points)

$n \leq 100$

Subtask 6 (23 points)

$n \leq 2\,000$

Subtask 7 (16 points)

No additional constraints.