题目背景

Source: AMPPZ 2019.

题目描述

在克拉科夫参观瓦维尔城堡时，你的团队被幽灵困在了一个古老的密室中。除非你们能回答他的问题，否则他不会放你们出去。

墙上挂着 $n$ 幅画作——如果将墙面视为标准的欧几里得平面，这些画作都是轴对齐的矩形。对于每幅画作，你都确切知道其尺寸和起始位置。在某个时刻——我们称之为时刻 0——幽灵开始移动这些画作，每幅画以各自的方向和速度移动。由于你们团队观察力敏锐，可以轻松推测出每幅画的确切速度。

一段时间后，幽灵停止了表演并开始提出棘手的问题。每个问题由两个数字 $l$ 和 $r$ 组成，表示表演的某些时刻。你必须告诉幽灵在 $l$ 到 $r$ 之间是否存在某个时刻，墙上的某个点同时被所有画作覆盖。如果是这样，你还需确定在 $l$ 到 $r$ 之间所有画作的最大可能公共面积。

如果你们想离开这个房间，最好给幽灵正确的答案！

输入格式

本题单个测试点内有多组测试数据。

输入的第一行包含测试数据组数 $z$ ($1 \le z \le 4000$)。每组测试数据的格式如下：

每组测试数据的第一行包含画作数量 $n$ ($1 \le n \le 100000$)。接下来的 $n$ 行每行包含六个数字
$x_1, y_1, x_2, y_2, v_x, v_y$
($-1000000 \le x_1 < x_2 \le 1000000$；
$-1000000 \le y_1 < y_2 \le 1000000$；
$-1000000 \le v_x, v_y \le 1000000$)，
其中 $(x_1, y_1)$ 是画作左下角的坐标，$(x_2, y_2)$ 是右上角的坐标，$(v_x, v_y)$ 是其速度向量。这意味着在时刻 $t$，左下角位于点 $(x_1 + t v_x, y_1 + t v_y)$，右上角位于 $(x_2 + t v_x, y_2 + t v_y)$。

接下来一行包含幽灵的问题数量 $q$ ($1 \le q \le 100000$)。随后的 $q$ 行每行包含两个实数 $l$, $r$ ($0 \le l \le r \le 1000000$)，小数点后最多 4 位，表示幽灵询问的闭时间区间 $[l, r]$。

所有测试数据中画作的总数不超过 1000000。
所有测试数据中问题的总数也不超过 1000000。

输出格式

对于幽灵的每个问题，输出一个实数——给定时间区间内所有画作交集的最大面积。如果绝对误差或相对误差不超过 $10^{-6}$，你的答案将被视为正确。换句话说，如果你的程序输出 $a$ 而正确值为 $b$，当满足以下条件时答案被接受：

交集可能为空——此时你的程序应输出 $0$ ($\pm 10^{-6}$)。

2
2
0 0 1 1 1 1
1 1 2 2 -1 -1
3
0 0
0.25 0.25
0 2
3
0 0 1 1 2 2
0 0 1 1 1 1
1 1 2 2 -1 -1
1
0 2

0.000000000
0.250000000
1.000000000
0.444444444