考古学家发现了古代 ACM 文明的遗迹，他们想要重建它。

这些遗迹在 $x-y$ 平面上构成了一个闭合路径，该路径有 $n$ 个端点。端点分别位于 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$。对于 $1 < i \le n$，端点 $i$ 和端点 $i-1$ 相邻，此外端点 $1$ 和端点 $n$ 也相邻。任意两个相邻端点之间的距离均为正整数。

为了重建，他们需要在每个端点处建造一个圆柱形柱子，端点 $i$ 处柱子的半径为 $r_i$。所有柱子均垂直于 $x-y$ 平面，且对应的端点位于柱子的中心线上。我们称两个柱子是相邻的，当且仅当它们对应的端点是相邻的。对于任意两个相邻的柱子，必须满足外切，否则将违背古代 ACM 文明的美学。如果两个柱子不相邻，则没有约束，即使它们相互重叠。

注意 $r_i$ 必须不小于 $0$，因为我们不能建造半径为负的柱子，且半径为 $0$ 的柱子是可以接受的，因为这类柱子在它们的邻居中仍然存在。

给定 $n$ 个端点的坐标，你的任务是找到 $r_1, r_2, \dots, r_n$，使得所有柱子的底面积之和尽可能小。

样例

例如，如果端点位于 $(0, 0), (11, 0), (27, 12), (5, 12)$，我们可以选择 $(r_1, r_2, r_3, r_4) = (3.75, 7.25, 12.75, 9.25)$。底面积之和等于 $3.75^2\pi + 7.25^2\pi + 12.75^2\pi + 9.25^2\pi = 988.816 \dots$。注意，我们对重叠部分的面积进行了多次计算。

如果存在多种方案能产生最小的底面积之和，你可以输出其中任意一种。

输入格式

第一行包含一个整数 $t$，表示测试用例的总数。接下来描述各个测试用例。

每个测试用例的第一行包含一个正整数 $n$，表示闭合路径的大小。接下来的 $n$ 行，每行包含两个整数 $(x_i, y_i)$，表示第 $i$ 个端点的坐标。

• $1 \le t \le 100$
• $3 \le n \le 10^4$
• $|x_i|, |y_i| \le 10^4$
• 任意两个相邻端点之间的距离均为正整数。

输出格式

如果不存在这样的解，则输出一行 "IMPOSSIBLE"（不含引号）。否则，在第一行输出最小的底面积之和，然后在接下来的 $n$ 行中，第 $i$ 行输出一个数字 $r_i$，保留小数点后两位。

如果存在多种方案能产生最小的底面积之和，你可以输出其中任意一种。

样例

输入 1

3
4
0 0
11 0
27 12
5 12
5
0 0
7 0
7 3
3 6
0 6
5
0 0
1 0
6 12
3 16
0 12

输出 1

988.82
3.75
7.25
12.75
9.25
157.08
6.00
1.00
2.00
3.00
0.00
IMPOSSIBLE