在集结了圣堂武士、黑暗圣堂武士、净化者和塔达林之后，阿塔尼斯的团队计划收复艾尔（星灵的家园）并摧毁堕落的萨尔那加人埃蒙。为了削弱埃蒙的势力，阿塔尼斯首先必须摧毁艾尔地下为大型灵能矩阵供能的能量结构。
能量结构包含 $N$ 个节点，由 $N-1$ 条无向道路连接，使得从任何节点都可以通过道路到达其他任何节点。节点编号为 $1$ 到 $N$。第 $i$ 个节点拥有一个能量水晶，存储了 $W_i$ 单位的能量。当阿塔尼斯攻击第 $i$ 个节点时，他有 $P_i$ 的概率成功摧毁该能量水晶，并使能量结构损失该节点所贡献的全部 $W_i$ 单位能量。（如果他未能摧毁能量水晶，该节点不会发生任何变化。）
在旗舰亚顿之矛上，阿塔尼斯将在虚拟的能量结构上进行一些模拟，以帮助他决定最佳策略。阿塔尼斯总共将进行 $Q$ 次模拟。在每次模拟中，他将从所有连通块的集合中等概率随机选择一个连通块。（如果一个节点集合中的任意节点都能在不经过集合外节点的情况下到达该集合中的其他任何节点，则称该节点集合为连通块。作为特殊情况，任何单个节点也是一个连通块。）然后，他将尝试攻击该块中的所有节点（如上所述），模拟将报告能量结构损失的能量总单位数。（虚拟能量结构在每次模拟之间会重置。）
在完成所有模拟后，阿塔尼斯将得到 $Q$ 个整数（每个整数代表损失的能量总数）。为了分析数据，他会将这些整数按非递减顺序排序。
请问这个排序数组中第 $K$ 个整数的期望值是多少？（$K$ 从 $1$ 开始计数。）
输入格式
输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的格式如下：
- 第一行包含三个整数 $N$、$Q$ 和 $K$。
- 接下来 $N-1$ 行，每行包含两个整数 $U_i$ 和 $V_i$，表示节点 $U_i$ 和另一个节点 $V_i$ 之间有一条道路。（所有这些节点对均不相同。）
- 一行包含 $N$ 个整数 $W_i$，表示第 $i$ 个节点水晶中存储的能量单位数。
- 一行包含 $N$ 个整数 $P_i$，表示阿塔尼斯攻击第 $i$ 个节点时成功的百分比概率。
输出格式
对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是排序后列表中第 $K$ 个数字的期望值。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。
数据范围
- $1 \le T \le 30$
- $1 \le N \le 200$
- $1 \le Q \le 50$
- $1 \le K \le Q$
- $1 \le U_i, V_i \le N$
- $0 \le W_i \le 50000$
- $0 \le \sum_{i=1}^{N} W_i \le 50000$
- $0 \le P_i \le 100$
样例
样例输入 1
3 1 2 2 1 50 3 1 1 3 2 1 2 1 1 1 100 100 100
样例输出 1
Case #1: 0.7500000000 Case #2: 1.6666666667
说明
在案例 #1 中，只有一个节点，拥有 1 单位能量。攻击该节点有 50% 的概率将其摧毁。由于该节点是唯一的连通块，每次模拟都会选择它。两次模拟的可能结果及排序后的列表如下：
- 成功，成功：1 1
- 成功，失败：0 1
- 失败，成功：0 1
- 失败，失败：0 0
在此情况下，所有结果出现的概率相等，因此位置 2 的期望值为 $\frac{1+1+1+0}{4} = 0.75$。
在案例 #2 中，有三个节点，连接方式为 1-2-3，每个节点拥有 1 单位能量，且如果阿塔尼斯攻击它们，则必定被摧毁。连通块有：{1}、{2}、{3}、{1, 2}、{2, 3} 和 {1, 2, 3}。（注意 {1, 3} 不是一个连通块，因为如果不经过块外的节点，就无法从 1 到达 3。）模拟将等概率随机选择其中一个。由于各块中摧毁的能量单位数分别为 1、1、1、2、2 和 3，因此列表中第一个（也是唯一一个）元素的期望值为 $\frac{10}{6}$。