数学家 Mary 几年前开了一家面包店，但久而久之，她对总是烘焙同样的矩形和圆形蛋糕感到厌倦。为了迎接下一个生日，她想烘焙一个“不规则”蛋糕，其定义为 $x=0$ 到 $x=W$ 之间两条“折线”所围成的区域。这两条折线分别被称为下边界和上边界。

形式上，折线由一系列从左到右的点 $(P_0, P_1, \dots, P_n)$ 定义。连续的点相连形成一系列线段，这些线段共同构成了折线。

今天是 Mary 的生日，她烘焙了一个由两条折线围成的不规则蛋糕，这两条折线分别有 $L$ 个点和 $U$ 个点。在唱完“生日快乐”歌后，她想进行 $G-1$ 次垂直切割，将蛋糕分成 $G$ 块面积相等的切片，以便与所有客人分享。然而，不规则的蛋糕形状使得这项任务相当棘手。你能帮她决定在哪里进行切割吗？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含四个整数：$W$（蛋糕的宽度）、$L$（下边界上的点数）、$U$（上边界上的点数）和 $G$（聚会的客人数量）。

随后是 $L$ 行，指定下边界。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示下边界上第 $i$ 个点的坐标。接着是 $U$ 行，指定上边界。第 $j$ 行包含两个整数 $x_j$ 和 $y_j$，表示上边界上第 $j$ 个点的坐标。

输出格式

对于每个测试用例，输出 $G$ 行。第一行应为 "Case #x:"，其中 $x$ 是用例编号（从 1 开始）。接下来的 $G-1$ 行应包含进行切割的 $x$ 坐标，按从最左侧切割到最右侧切割的顺序排列。

相对误差或绝对误差不超过 $10^{-6}$ 的答案将被视为正确。

数据范围

$1 \le T \le 100$。 $1 \le W \le 1000$。 $2 \le L \le 100$。 $2 \le U \le 100$。 所有坐标均为 $-1000$ 到 $1000$ 之间的整数（含边界）。 两条边界最左侧点的 $x$ 坐标均为 $0$。 两条边界最右侧点的 $x$ 坐标均为 $W$。 同一边界上的点按 $x$ 坐标递增排序。 同一边界上的点具有不同的 $x$ 坐标。 在 $0$ 到 $W$（含边界）的所有 $x$ 位置上，下边界始终严格低于上边界。（换句话说，在每个 $x$ 位置，下边界的 $y$ 坐标都小于上边界的 $y$ 坐标。）

样例

样例输入 1

2
15 3 3 3
0 6
10 8
15 9
0 10
5 11
15 13
8 3 4 2
0 2
5 4
8 3
0 5
3 4
4 7
8 5

样例输出 1

Case #1:
5.000000
10.000000
Case #2:
4.290588