Igor 是一个几何迷，所以他给自己买了一个平面以及一个由 $n$ 个互不相同的点组成的集合 $P$，其中第 $i$ 个点的位置为 $(x_i, y_i)$。

对 Igor 来说，在这之中找出距离最远的两个点简直是易如反掌。他很快就觉得无聊了，于是决定想出 $q$ 个实数 $\alpha_1, \alpha_2, \alpha_3, \dots, \alpha_q$。对于这些数中的每一个，Igor 都想知道：如果他将每个点的 $x$ 坐标缩放 $\alpha_j$ 倍，任意两点之间的最大可能距离是多少。正式地讲，他希望在集合 $(x_i \cdot \alpha_j, y_i)$ 中找到距离最远的两个点。请帮助 Igor！

输入格式

每个输入包含多个测试用例。第一行包含两个整数 $t$ 和 $g$（$1 \le t \le 250\,000$，$0 \le g \le 9$）——测试用例的数量以及表示这些测试用例可能满足的附加限制的子任务编号。接下来是 $t$ 个测试用例。

每个测试用例开头包含两个整数 $n$ 和 $q$（$2 \le n \le 500\,000$，$1 \le q \le 500\,000$）——点的数量和询问的数量。

接下来的 $n$ 行包含每个点的坐标 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$）。保证同一个测试用例中的所有点都是互不相同的。

接下来的 $q$ 行包含询问，每个询问由一个实数 $\alpha_j$（$1 \le \alpha_j \le 10^9$）表示——即缩放系数。

记所有测试用例中 $n_i$ 的总和为 $N$，所有测试用例中 $q_i$ 的总和为 $Q$。保证 $N, Q \le 500\,000$。

输出格式

对于每个测试用例，输出 $q$ 个实数：表示第 $i$ 个询问的答案。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。更具体地，设你的答案为 $a$，裁判答案为 $b$，当满足 $\frac{|a-b|}{\max(b,1)} \le 10^{-6}$ 时，你的答案将被判定为正确。

样例

输入样例 1

2 0
5 2
0 0
1 1
0 2
-1 3
0 4
1
2.5
8 4
0 0
6 11
7 13
4 14
0 15
-4 14
-7 13
-6 11
2
1
1.25
1.5

输出样例 1

4.000000
5.385165
28.000000
15.000000
17.500000
21.000000

子任务

本题的测试集由 9 个子任务组成。只有当你的程序通过该子任务中的所有测试点以及所有依赖的子任务时，你才能获得该子任务的分数。“离线评测”（Offline-evaluation）意味着你不会立即获得该子任务的反馈，只能在比赛结束后看到结果。

“随机点”意味着每个坐标都是在 $-10^9$ 到 $10^9$ 之间独立且均匀随机生成的。