407514: GYM102821 F Farm

Fish is retired from programming, so he goes back home and becomes a farmer.

It is important to know the total sunshine time for a specific position in a day. If we assume that his farm is a segment from $$$(0, 0)$$$ to $$$(W, 0)$$$, the sun above can be seen to move from $$$(0, H)$$$ to $$$(W, H)$$$ at a constant speed. Whatever the precise value for the speed is, what we care is just the relevant sunshine time in a day, which is the ratio of actual sunshine time to the total time for the sun moving from the start to the end.

At the same time, there are $$$N$$$ stationary clouds on the sky in a day, and each cloud can be regarded as a segment paralleling to the farm. You should know that the light moves straightly, so the clouds may block the sunshine in some time for some places.

Please help Fish figure out the relevant sunshine time in a day for some positions.

The first line of input contains an integer $$$T$$$, representing the number of test cases.

Then for each test case:

The first line contains four integers $$$N, W, H, Q$$$, the number of clouds, and range of the farm, the height of the sun and the number of queries. Then $$$N$$$ lines follow, each line containing three integers $$$x_1, x_2, y$$$, which means that there is a cloud from $$$(x_1, y)$$$ to $$$(x_2, y)$$$.

Then $$$Q$$$ lines follow, each line containing one integer $$$x$$$, which means that Fish wants to know the answer for position $$$(x, 0)$$$.

For each test case, you should output Case $$$x$$$: first, where $$$x$$$ indicates the case number starting from $$$1$$$. Then $$$Q$$$ lines follow, each line containing a real number representing the answer.

Your answer will be consider correct if its absolute error does not exceed $$$10^{-6}$$$.

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

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$$$

For $$$90\%$$$ test cases: $$$N \le 100$$$, $$$Q\le 1000$$$