在参观克拉科夫的瓦维尔城堡时，你们的团队被幽灵困在了一个古老的房间里。除非回答他的问题，否则他不会放你们离开。

墙上有 $n$ 幅画——如果我们把墙看作标准的欧几里得平面，这些画就是轴对齐的矩形。对于每一幅画，你都清楚地知道它的尺寸和起始位置。在某个时刻——我们称之为时刻 0——幽灵开始移动这些画，每一幅画都以各自的方向和速度运动。作为一个善于观察的团队，你可以轻松地推断出每一幅画的确切速度。

过了一段时间，幽灵停止了表演，开始提出棘手的问题。每个问题包含两个数字 $l$ 和 $r$，代表表演过程中的某些时刻。你必须告诉幽灵在 $l$ 到 $r$ 之间是否存在某个时刻，使得墙上的某一点同时被所有画覆盖。如果存在，你还需要确定在时刻 $l$ 到 $r$ 之间，所有画的交集所能达到的最大面积。

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

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 4000$)。接下来是各个测试用例，每个测试用例的格式如下：

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

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

所有测试用例中画的总数不超过 $1\,000\,000$。所有测试用例中问题的总数也不超过 $1\,000\,000$。

输出格式

对于幽灵的每一个问题，输出一个实数——在给定时间区间内，所有画的交集所能达到的最大面积。如果你的答案与正确值 $b$ 的绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。换句话说，如果你的程序输出 $a$，当满足 $\frac{|a-b|}{\max(1, b)} \le 10^{-6}$ 时，答案被接受。

交集可能为空——在这种情况下，你的程序应输出 $0$ ($\pm 10^{-6}$)。

样例

样例输入 1

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

样例输出 1

0.000000000
0.250000000
1.000000000
0.444444444