소방차 출동

문제

어떤 나라의 국토는 2차원 평면이다. 하늘을 나는 교통수단이 없어서 도로를 달리는 자동차가 가장 빠른 이동 수단이다. 도로는 평면 위에 놓인 $n$ 개의 선분이고, 자동차는 도로 위에서만 움직인다.

화재가 일어나면 소방차가 소방서에서 출발한다. 소방서는 도로 위의 여러 지점에 있다. 소방차는 화재 지점과의 거리가 $R$ 이하인 곳에 도착하면 그 자리에서 호스로 불을 끈다. 화재 지점까지 갈 필요는 없고, 도로 위의 어느 점이든 화재 지점과의 거리가 $R$ 이하이기만 하면 된다.

도로의 배치와 소방서의 위치, 그리고 $Q$ 개의 화재 지점이 주어진다. 각 화재마다 소방차가 달려야 하는 최소 거리를 구한다. 소방차는 어느 소방서에서 출발해도 되고, 이동 거리는 도로를 따라 잰다.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스는 다음과 같이 구성된다.

첫 줄에 도로의 수 $n$ ( $1 \le n \le 1\,000$ )과 진압 반경 $R$ ( $0 \le R \le 1\,000$ )이 정수로 주어진다.
이어지는 $n$ $n$ 개의 줄에 도로 하나의 정보가 $sx_i$ $s x_{i}$ , $sy_i$ $s y_{i}$ , $ex_i$ $e x_{i}$ , $ey_i$ $e y_{i}$ , $m_i$ $m_{i}$ , $c_{i1}$ $c_{i 1}$ , $c_{i2}$ $c_{i 2}$ , $\dots$ $\dots$ , $c_{im_i}$ $c_{i m_{i}}$ 순서로 주어진다 ( $0 \le sx_i, sy_i, ex_i, ey_i \le 1\,000$ $0 \leq s x_{i}, s y_{i}, e x_{i}, e y_{i} \leq 1000$ , $0 \le m_i \le 100$ $0 \leq m_{i} \leq 100$ , $1 \le \sum m_i \le 100$ $1 \leq \sum m_{i} \leq 100$ , $0 \le c_{ij} \le 1$ $0 \leq c_{ij} \leq 1$ ).
- $i$ 번째 도로는 $(sx_i, sy_i)$ 와 $(ex_i, ey_i)$ 를 잇는 선분이다.
- $m_i$ 는 $i$ 번째 도로 위에 있는 소방서의 개수이다.
- $c_{ij}$ 는 $i$ 번째 도로 위에서 소방서가 놓인 위치를 나타내는 실수이고, 그 소방서의 좌표는 $(sx_i \times (1 - c_{ij}) + ex_i \times c_{ij},\ sy_i \times (1 - c_{ij}) + ey_i \times c_{ij})$ 이다.
- $c_{ij}$ 를 제외한 모든 값은 정수이다.
다음 줄에 화재의 수 $Q$ ( $1 \le Q \le 1\,000$ )가 주어지고, 이어지는 $Q$ 개의 줄에 화재가 일어난 지점의 좌표 $x_i$ , $y_i$ ( $0 \le x_i, y_i \le 1\,000$ )가 정수로 주어진다.

서로 다른 두 도로는 많아야 한 점에서 만난다.

출력

각 화재마다 소방차가 달려야 하는 최소 거리를 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래는 항상 여섯 자리를 쓰고, 모자라는 자리는 0으로 채운다. 불을 끌 수 없는 화재라면 -1을 출력한다.