平面上有 $n$ 个青色点 $C_1, \cdots, C_n$ 和 $n$ 个兰色点 $B_1, B_2, \cdots, B_n$。你的任务是：

1. 找到一个位置，放置一个白色点 $W$
2. 将白色点、青色点、兰色点配对成 $n$ 个三角形，满足每个青色点和兰色点恰好在一个三角形中。
   • 我们假设对每个 $1 \leq i \leq n$，对应的三角形为 $\triangle WC_iB_{p_i}$，这样 $p$ 可被视为一个 $1 \sim n$ 的排列。
3. $\angle C_iWB_{p_i}$ 不能是一个锐角。即，$\angle C_iWB_{p_i} \geq \pi/2$

构造任意一个合法方案。可以证明，解总是存在。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含一个整数 $T$，表示数据组数。对于每组数据：

输入的第一行包含一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x$ 和 $y$，描述点 $C_i$ 的坐标。

接下来 $n$ 行，每行两个整数 $x$ 和 $y$，描述点 $B_i$ 的坐标。

输入数据保证所有给定的 $2n$ 个点互不相同。

输出格式

对于每组数据：

输出的第一行包含两个实数 $x_W, y_W$，表示你构造的点 $W$ 的坐标。你需要保证 $-10^9 \leq x_W, y_W \leq 10^9$。

接下来一行，输出 $n$ 个整数 $p_1, p_2, \cdots, p_n$，表示你构造的排列 $p$。

如果有多种合法的解，你可以输出任意一种。

样例数据

样例输入

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

样例输出

-1.230077554196 2.883883476483
3 5 1 6 4 2

如何测试你的输出

首先，在本题中，我们允许出现点重合的情况。即，虽然我们给定的 $2n$ 个点互不相同，但我们允许你构造的点 $W$ 与任意一个给定的点位于相同的位置。

对于 $\angle C_iWB_{p_i}$，如果出现了 $C_i = W$ 或 $B_{p_i} = W$ 的情况，我们会认为该角为一个恰好 $180$ 度的平角。

为了避免可能的浮点误差，我们会采用以下方式检查你的输出是否合法：

• 令 $\varepsilon = 10^{-6}$
• 对每个 $1 \leq i \leq n$：
  • 令 $r = |C_iW|^2 + |B_{p_i}W|^2$ 且 $d = |C_iB_{p_i}|^2$
  • 我们会检查 $r \leq \max(d + \varepsilon, d \cdot (1 + \varepsilon))$ 是否成立。即，在允许有至多 $10^{-6}$ 的绝对或相对误差的情况下 $r \leq d$ 是否成立。

子任务

对于所有数据，保证 $1 \leq n \leq 2 \times 10^5$，$1 \leq \sum n \leq 2 \times 10^5$，$-10^6 \leq x,y \leq 10^6$。

请注意，子任务的限制中，并没有包含对 $\sum n$ 的限制。在所有子任务中都可能会出现 $\sum n$ 达到 $2 \times 10^5$ 级别的数据。

子任务一（6 分）

$n = 1$

子任务二（8 分）

$n \leq 2$

子任务三（8 分）

$n \leq 3$

子任务四（14 分）

$n \leq 16$

子任务五（25 分）

$n \leq 100$

子任务六（23 分）

$n \leq 2\,000$

子任务七（16 分）

没有额外的限制。