你正站在机场的 0 点位置。一条长度为 $X$ 的走廊通向登机口，你的飞机即将起飞。走廊里有一些自动人行道，每条人行道的移动速度为 $w_i$。当你在人行道上行走或奔跑时，你的移动速度为（你的速度 + $w_i$）。人行道的位置是固定的；它们只会让你移动得更快。人行道之间互不重叠：在走廊的任何给定点上，最多只有一条人行道，但一条人行道可以在另一条人行道结束的地方开始。

你正常的行走速度为 $S$。你担心赶不上飞机，所以你可以进行短时间的奔跑——你最多可以以速度 $R$ 奔跑总计 $t$ 秒。你不必连续奔跑 $t$ 秒：你可以将这 $t$ 秒拆分成任意数量的时间段，甚至可以不使用其中的一部分时间。

假设你选择何时行走、何时奔跑以尽快到达登机口，请问你需要多长时间才能到达？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含五个整数：$X$（走廊长度，单位为米）、$S$（你的行走速度，单位为米/秒）、$R$（你的奔跑速度，单位为米/秒）、$t$（你最多可以奔跑的时间，单位为秒）和 $N$（人行道的数量）。

接下来的 $N$ 行，每行包含三个整数：$B_i$、$E_i$ 和 $w_i$ —— 分别表示人行道的起点、终点（距离起点的距离，单位为米）以及人行道的速度（单位为米/秒）。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是你以最优策略行走和奔跑到达 $X$ 点所需的时间（单位为秒）。相对或绝对误差不超过 $10^{-6}$ 的答案将被视为正确。

数据范围

$1 \le T \le 40$。 $1 \le S < R \le 100$。 $1 \le w_i \le 100$。 $0 \le B_i < E_i \le X$。 $E_i \le B_{i+1}$。

小数据（测试集 1 - 可见；8 分）

$1 \le t \le 100$。 $1 \le X \le 100$。 $1 \le N \le 20$。

大数据（测试集 2 - 隐藏；10 分）

$1 \le t \le 10^6$。 $1 \le X \le 10^6$。 $1 \le N \le 1000$。

样例

样例输入 1

3
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1

样例输出 1

Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238

说明

第一个样例的最优解是立即开始奔跑，并持续奔跑一秒。