若点集 $S$ 关于直线 $\ell$ 对称，当且仅当存在 $s' \in S$ 使得对于所有 $s \in S$，点 $s$ 和 $s'$ 关于直线 $\ell$ 对称。

记两点 $a$ 和 $b$ 之间的距离为 $d(a, b)$。两个非空点集 $A$ 和 $B$ 之间的距离定义为 $\inf \{d(a, b) : a \in A, b \in B\}$。非空实数集 $S$ 的下确界是满足对于所有 $s \in S$ 都有 $x \le s$ 的最大值 $x$。

给定 $n$ 条直线 $\ell_1, \ell_2, \dots, \ell_n$，其中两条或多条直线可能重合。对于点 $s$，定义 $C(s)$ 为所有满足 $s \in S$ 且 $S$ 关于所有 $\ell_i$ ($i = 1, 2, \dots, n$) 对称的集合 $S$ 的交集。

共有 $q$ 次询问。对于每次询问，给定两点 $A$ 和 $B$，求 $C(A)$ 和 $C(B)$ 之间的距离。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示直线的数量和询问的数量。

接下来的 $n$ 行，每行包含四个整数 $x_{P_i}, y_{P_i}, x_{Q_i}, y_{Q_i}$，表示直线 $\ell_i$ 经过点 $P_i$ 和 $Q_i$。保证 $x_{P_i} = x_{Q_i}$ 或 $y_{P_i} = y_{Q_i}$。任意两条直线可能重合。

接下来的 $q$ 行，每行包含四个整数 $x_{A_i}, y_{A_i}, x_{B_i}, y_{B_i}$，表示点 $A_i$ 和 $B_i$ 的坐标。

保证输入中所有坐标的绝对值不超过 $10^9$。 保证所有测试数据中 $n$ 的总和与 $q$ 的总和均不超过 $10^5$。

输出格式

对于每组测试数据：

对于每次询问，输出 $C(A)$ 和 $C(B)$ 之间的距离。

如果输出的距离与标准答案的相对误差或绝对误差不超过 $10^{-9}$，则视为正确。

样例

样例输入 1

4
1 1
0 0 1 0
-1 -2 2 1
2 1
0 0 1 0
0 0 0 1
-1 -2 2 1
3 1
0 0 1 0
0 0 0 1
0 0 1 1
-1 -2 2 1
3 1
0 0 1 0
0 0 0 1
0 0 1 2
-1 -2 2 1

样例输出 1

3.162277660168
1.414213562373
0.000000000000
0.000000000000

样例输入 2

5
1 1
-8 1 -8 10
-7 -5 -4 -6
2 2
-1 -10 -1 -8
10 9 9 10
2 10 -10 5
-4 4 -3 -3
3 1
-5 -10 -5 6
6 10 8 8
7 -2 4 -5
0 -9 -6 -3
3 3
9 8 10 7
1 5 -9 5
4 -2 -3 -9
6 6 -6 -8
2 -7 10 -3
3 -8 8 -9
1 3
10 -9 10 -7
-2 -7 -2 6
-2 9 -9 2
-6 -7 -7 -9

样例输出 2

3.162277660168
7.810249675907
7.071067811865
7.211102550928
0.000000000000
0.000000000000
0.000000000000
13.000000000000
9.899494936612
2.236067977500