Description

Igor 是一位几何学爱好者，他为自己买了一张平面和一组 $P$，包含 $n$ 个不同的点，第 $i$ 个点坐标为 $(x_i, y_i)$。

他很快就能找出这组点中距离最远的两点。很快他觉得这太简单了，于是想出 $q$ 个实数 $\alpha_1, \alpha_2, \ldots, \alpha_q$。对于每一个 $\alpha_j$，Igor 都想知道：如果将所有点的 $x$ 坐标按 $\alpha_j$ 缩放后，点集中最远的两点间的最大距离是多少。形式化地说，他关心集合 $(x_i \cdot \alpha_j, y_i)$ 中最远两点的距离。请你帮帮 Igor！

Input Format

每组输入包含多组测试数据。第一行包含两个整数 $t$ 和 $g$（$1 \leq t \leq 250\,000$，$0 \leq g \leq 9$），分别表示测试数据组数和当前测试组编号（用于指示额外限制）。接下来是 $t$ 组测试数据。

每组测试数据的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 500\,000$，$1 \leq q \leq 500\,000$），分别表示点的数量和查询的数量。

接下来的 $n$ 行，每行两个整数 $x_i$ 和 $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$），表示每个点的坐标。保证同一组内所有点互不相同。

接下来的 $q$ 行，每行一个实数 $\alpha_j$（$1 \leq \alpha_j \leq 10^9$），表示一次缩放的系数。

记所有测试数据中 $n_i$ 的和为 $N$，所有 $q_i$ 的和为 $Q$。保证 $N, Q \leq 500\,000$。

Output Format

对于每组测试数据，输出 $q$ 个实数，第 $i$ 个为对应查询的答案。

你的答案只要绝对误差或相对误差不超过 $10^{-6}$ 即可。更具体地说，若 $a$ 为你的答案，$b$ 为标准答案，则只要 $\frac{|a-b|}{\max(b, 1)} \leq 10^{-6}$，就被认为是正确的。

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

4.000000
5.385165
28.000000
15.000000
17.500000
21.000000

Hint

评分说明

本题测试数据共分为 9 组。只有通过某组所有测试点，且通过所有必需的前置组，才能获得该组分数。离线评测表示该组的评测结果将在比赛结束后公布。

随机点表示每个坐标均独立均匀地在 $-10^9$ 到 $10^9$ 之间随机生成。