Ekiya 镇上现代化的铁路系统遇到了一个重大障碍：一条南北走向的主干道。在高速公路的西侧已经建造并连接了 $W$ 个车站，在东侧也建造并连接了 $E$ 个车站。现在需要在西侧车站和东侧车站之间建立一个连接，但由于高速公路的阻隔，该连接必须通过天桥来建造。

Ekiya 正在评估哪些车站通过天桥连接最为方便。作为评估的一部分，她想知道随着每种可能的选择，系统中路径的平均长度（以车站数量计）会发生怎样的变化。

车站 $s$ 和 $t$ 之间的路径是一个由不同车站组成的列表，以 $s$ 开头，以 $t$ 结尾，且列表中任意两个相邻的车站都共享一个连接。该铁路系统目前在西侧有 $W$ 个车站，通过 $W-1$ 条连接相连，使得任意两个不同的西侧车站之间恰好存在一条路径。同样，东侧有 $E$ 个车站，通过 $E-1$ 条连接相连，使得任意两个不同的东侧车站之间恰好存在一条路径。在建立连接一个西侧车站和一个东侧车站的天桥后，任意两个不同的车站之间将恰好存在一条路径。

完整地图是指拥有 $W+E-1$ 条连接且任意一对车站之间恰好存在一条路径的地图。完整地图的平均距离是所有不同车站对之间路径长度的平均值。路径的长度定义为定义该路径的车站列表长度减 1（例如，直接相连的车站之间的路径长度为 1）。

作为一个例子，下图展示了西侧有 $W=2$ 个车站，东侧有 $E=3$ 个车站的情况。图中展示了 2 种可能的过街天桥方案。

下表显示了如果建造每种天桥，各车站对之间的路径长度。

给定当前的车站和连接，以及一系列天桥连接的选项，请通过计算如果仅建造该选项作为天桥连接时所形成的地图的平均距离，来帮助 Ekiya。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $W$、$E$ 和 $C$，分别表示西侧车站数量、东侧车站数量以及天桥连接的选项数量。西侧车站编号为 $1$ 到 $W$，东侧车站编号为 $1$ 到 $E$。

测试用例的第二行包含 $W-1$ 个整数 $X_1, X_2, \dots, X_{W-1}$，表示西侧车站中第 $i$ 条现有连接连接了西侧车站 $i+1$ 和 $X_i$。

测试用例的第三行包含 $E-1$ 个整数 $F_1, F_2, \dots, F_{E-1}$，表示东侧车站中第 $j$ 条现有连接连接了东侧车站 $j+1$ 和 $F_j$。

最后，$C$ 行描述了天桥连接的选项。第 $k$ 行包含两个整数 $A_k$ 和 $B_k$，分别表示第 $k$ 个天桥连接选项所连接的西侧车站和东侧车站。

输出格式

对于每个测试用例，输出一行，包含 Case #x: y1 y2 ... yC，其中 $x$ 是测试用例编号（从 1 开始），$y_k$ 是将第 $k$ 个选项作为天桥连接添加到所有现有连接后所形成的地图的平均距离。

如果 $y_1, y_2, \dots$ 和 $y_k$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则被视为正确。

数据范围

内存限制：2 GB。 $1 \le T \le 100$。 $2 \le W \le 10^5$。 $2 \le E \le 10^5$。 $i+1 \le X_i \le W$，对于所有 $i$。（这意味着每对西侧车站之间恰好存在一条路径。） $j+1 \le F_j \le E$，对于所有 $j$。（这意味着每对东侧车站之间恰好存在一条路径。） $1 \le A_k \le W$，对于所有 $k$。 $1 \le B_k \le E$，对于所有 $k$。 $(A_k, B_k) \neq (A_\ell, B_\ell)$，对于所有 $k \neq \ell$。（每个列出的天桥连接都是不同的。）

样例

样例输入 1

3
2 3 2
2
3 3
1 1
2 3
3 4 2
2 3
3 3 4
1 3
1 2
3 4 1
2 3
3 3 4
2 2

样例输出 1

Case #1: 2.0 1.8
Case #2: 2.19047619 2.47619048
Case #3: 2.2857142857

说明

样例 1 已在题目描述中解释并展示。样例 2 和样例 3 如下图所示。