To ask why we fight? Is to ask why the leaves fall? It is in the nature. Perhaps there is a better question. Why do we fight? To protect home and family, To preserve balance and bring harmony. For my kind, The true question is what is worth fighting for. —CG

Chen 正在练习功夫。他使用“气爆”来使能量点分裂。

最初，无限二维平面上有 $n$ 个能量点。每一秒，每个能量点都会检查其四个相邻位置（上 $(0, 1)$，下 $(0, -1)$，左 $(-1, 0)$，右 $(1, 0)$）。如果该位置没有能量点，则会在该位置生成一个新的能量点。

Chen 想提前了解练习的进展。他会给你 $q$ 次询问，每次询问包含一个整数 $t$，你需要求出 $t$ 秒后所有能量点构成的凸包的面积。

输入格式

第一行包含一个整数 $T(1 \le T \le 11)$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $n, q(1 \le n, q \le 2 * 10^5)$，分别表示初始点的数量和询问次数。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $x, y(0 \le x, y \le 10^8)$，表示第 $i$ 个初始能量点的坐标。

随后 $q$ 行，每行包含一个整数 $t(0 \le t \le 10^8)$，表示秒数。

保证 $\sum n \le 5 * 10^5$，$\sum q \le 5 * 10^5$。

输出格式

对于每次询问，输出一行，表示答案。你的答案应保留一位小数。

样例

输入 1

2
3 3
2 3
4 3
1 1
1
2
3
3 3
4 1
3 4
2 1
2
3
4

输出 1

11.0
24.0
41.0
27.0
45.0
67.0