法师之间的战斗仍在继续！今天，Svetozar 召集了一支由 $n$ 名好法师组成的队伍，而 Arglwyddytywyllwch 则组建了一支由 $m$ 名邪恶法师组成的队伍。

每位法师都拥有通过施法进行攻击的能力，以及防御其他法师法术的能力，这些能力由特定的数值表示。战斗的结果及其精彩程度取决于这些能力。第 $i$ 位好法师的攻击力为 $a_i$，防御力为 $b_i$；第 $i$ 位邪恶法师的攻击力为 $c_i$，防御力为 $d_i$。

在战斗开始前，Svetozar 和 Arglwyddytywyllwch 将从各自的队伍中选择若干名连续的法师（即，如果选择了队伍中第 $L$ 位和第 $R$ 位法师，那么该队伍中第 $L+1, L+2, \dots, R-1$ 位法师也必须被选中）。只有被选中的法师才会参与战斗。

你是一位公正的、中立的旁观者，并不关心哪一方会获胜。你更关注战斗的精彩程度。如果不同阵营中至少有一对法师的战斗不够激烈，你就会感到不满。你定义第 $i$ 位好法师与第 $j$ 位邪恶法师之间的战斗强度 $f(i, j)$ 为他们攻击力之和与防御力之和的比值，即： $$f(i, j) = \frac{a_i + c_j}{b_i + d_j}$$

你定义好法师索引从 $p$ 到 $q$ ($p \le q$) 与邪恶法师索引从 $r$ 到 $s$ ($r \le s$) 之间的整场战斗强度为所有被选中的不同阵营法师对之间战斗强度的最小值，即： $$\min_{i=p}^{q} \min_{j=r}^{s} f(i, j)$$

在战斗开始前，你考虑了 $q$ 种假设情况：已知恰好有 $x$ 名好法师和恰好有 $y$ 名邪恶法师将被选中，即将到来的战斗可能达到的最大强度是多少？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

接下来是 $T$ 个测试用例的描述。每个描述的第一行包含三个整数 $n, m, q$ ($1 \le n, m, q \le 10^5$)：Svetozar 队伍中的法师数量、Arglwyddytywyllwch 队伍中的法师数量以及假设情况的数量。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$：好法师的攻击力。

第三行包含 $n$ 个整数 $b_1, \dots, b_n$：好法师的防御力。

第四行包含 $m$ 个整数 $c_1, \dots, c_m$：邪恶法师的攻击力。

第五行包含 $m$ 个整数 $d_1, \dots, d_m$：邪恶法师的防御力。

接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x \le n, 1 \le y \le m$)：假设情况中被选中的好法师数量和邪恶法师数量。

保证对于 $1 \le i \le n, 1 \le j \le m$，有 $1 \le a_i, b_i, c_j, d_j \le 1000$。同时保证所有测试用例中 $(n + m) \cdot q$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $q$ 行。每行包含一个实数：相应战斗可能达到的最大强度。如果答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

样例输入 1

2
3 4 5
1 1 1
2 3 4
6 7 8 9
5 6 7 8
1 1
1 2
2 1
3 3
3 4
1 1 1
1000
1
1
1000
1 1

样例输出 1

1.000000000
1.000000000
0.909090909
0.800000000
0.777777778
1.000000000

说明

在第一个测试用例中，好法师与每位邪恶法师之间的战斗强度为： 对于第一位好法师：1, 1, 1, 1； 对于第二位好法师：$\frac{7}{8}, \frac{8}{9}, \frac{9}{10}, \frac{10}{11}$； 对于第三位好法师：$\frac{7}{9}, \frac{4}{5}, \frac{9}{11}, \frac{5}{6}$。

在第二个测试用例中，只有两名法师，他们的战斗强度为 $\frac{1000+1}{1+1000} = 1$。