Fish 退休了，不再从事编程工作，而是回到了家乡成为了一名农夫。

了解一天中特定位置的日照总时长非常重要。假设他的农场是坐标系中从 $(0, 0)$ 到 $(W, 0)$ 的线段，太阳在一天中从 $(0, H)$ 移动到 $(W, H)$，且速度恒定。无论速度的具体数值是多少，我们关心的只是“相关日照时长”，即实际日照时长与太阳从起点移动到终点总时长之比。

同时，天空中一天内有 $N$ 朵静止的云，每朵云都可以看作一条平行于农场的线段。光线沿直线传播，因此云朵可能会在某些时间段遮挡某些位置的阳光。

请帮助 Fish 计算出某些位置在一天中的相关日照时长。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例： 第一行包含四个整数 $N, W, H, Q$，分别表示云的数量、农场的范围、太阳的高度以及查询的数量。

接下来 $N$ 行，每行包含三个整数 $x_1, x_2, y$，表示有一朵从 $(x_1, y)$ 到 $(x_2, y)$ 的云。

接下来 $Q$ 行，每行包含一个整数 $x$，表示 Fish 想知道位置 $(x, 0)$ 的答案。

输出格式

对于每个测试用例，首先输出 Case x:，其中 $x$ 表示从 1 开始的用例编号。 然后输出 $Q$ 行，每行包含一个表示答案的实数。

如果你的答案与标准答案的绝对误差不超过 $10^{-6}$，则视为正确。

样例

输入 1

2
1 4 4 5
1 3 2
0
1
2
3
4
2 4 4 5
1 2 2
2 3 3
0
1
2
3
4

输出 1

Case 1:
0.50000000
0.25000000
0.00000000
0.25000000
0.50000000
Case 2:
0.50000000
0.33333333
0.16666667
0.41666667
0.66666667

数据范围

$1 \le T \le 100$ $1 \le N \le 1000$ $1 \le W, H \le 10^6$ $1 \le Q \le 5 \times 10^5$ $0 \le x_1 < x_2 \le W$ $1 \le y < H$ 对于 90% 的测试用例：$N \le 100, Q \le 1000$