L. Symmetry: Closure
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

A point set $$$S$$$ is symmetric about a line $$$\ell$$$ if and only if there exists $$$s' \in S$$$ satisfying that $$$s'$$$ and $$$s$$$ are symmetric about the line $$$\ell$$$ for all $$$s \in S$$$.

Let us denote the distance between two points $$$a$$$ and $$$b$$$ as $$$d(a,b)$$$. The distance between two non-empty point sets $$$A$$$ and $$$B$$$ is $$$\inf \left\{d(a,b) : a \in A, \, b \in B \right\}$$$. The infimum of a non-empty real number set $$$S$$$ is the maximum value of $$$x$$$ which satisfies $$$x \le s$$$ for all $$$s \in S$$$.

Lines $$$\ell_1, \ell_2, \ldots, \ell_n$$$ are given, where two or more lines may coincide. For a point $$$s$$$, define $$$C(s)$$$ as the intersection of all sets $$$S$$$ satisfying $$$s \in S$$$ such that $$$S$$$ is symmetric about $$$\ell_i$$$ for all $$$i = 1, 2, \ldots, n$$$.

There are $$$q$$$ queries. For each query, given two points $$$A$$$ and $$$B$$$, find the distance between $$$C(A)$$$ and $$$C(B)$$$.

Input

There are multiple test cases. The first line of input contains an integer $$$T$$$ ($$$1\le T\le 10^5$$$), the number of test cases. For each test case:

The first line contains an integer $$$n$$$ and $$$q$$$ ($$$1\le n, q\le 10^5$$$): the number of lines and the number of points.

The $$$i$$$-th of the following $$$n$$$ lines contains four integers $$$x_{P_i}$$$, $$$y_{P_i}$$$, $$$x_{Q_i}$$$, and $$$y_{Q_i}$$$: the coordinates of $$$P_i$$$ and $$$Q_i$$$ such that $$$\ell_i$$$ passes through $$$P_i$$$ and $$$Q_i$$$. It is guaranteed that $$$x_{P_i} \ne x_{Q_i}$$$ or $$$y_{P_i} \ne y_{Q_i}$$$. Any two lines may coincide.

The $$$i$$$-th of the following $$$q$$$ lines contains four integers $$$x_{A_i}$$$, $$$y_{A_i}$$$, $$$x_{B_i}$$$, and $$$y_{B_i}$$$: the coordinates of $$$A_i$$$ and $$$B_i$$$.

It is guaranteed that the absolute value of all coordinates in the input does not exceed $$$10^9$$$.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$.

Output

For each test case:

For each query, output the distance between $$$C(A)$$$ and $$$C(B)$$$.

The distance you output will be considered correct if the relative error or absolute error to the jury does not exceed $$$10^{-9}$$$.

Examples
Input
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
Output
3.162277660168
1.414213562373
0.000000000000
0.000000000000
Input
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
Output
3.162277660168
7.810249675907
7.071067811865
7.211102550928
0.000000000000
0.000000000000
0.000000000000
13.000000000000
9.899494936612
2.236067977500