Vampire Escape (part 2)

A vampire is trapped in a rectangular room of height $H$ and width $W$ .

There are mysterious holes in the roof: due to strange room geometry, each hole projects a circular patch of sunlight (a sunspot) onto the floor. During the observation interval $[0, L]$ , the center of sunspot $i$ moves linearly as

x_{i} (t) = x_{i}^{(0)} + v_{x, i} t, y_{i} (t) = y_{i}^{(0)} + v_{y, i} t

while its radius $R_{i}$ is constant. Here $t$ denotes the current time. We only consider sunspots whose center is within the room boundaries; the moment the sunspot's center is outside the room, it does not cast any sunlight onto the floor.

Although the room is dim, faint sunlight leaks everywhere, and the vampire wishes to minimize his exposure to sunlight. He may choose any time $t \in [0, L]$ and then dash straight upward from the bottom wall to the top wall along a vertical line segment at some $x \in [0, W]$ .

If this vertical path intersects or even touches any sunspot present at time $t$ , the vampire is instantly incinerated. Otherwise, he survives and reaches the top wall.

Determine the total duration of time within $[0, L]$ during which there exists at least one vertical line $x \in [0, W]$ that gets from $(x, 0)$ to $(x, H)$ without touching any sunspot.

Input

The first line contains an integer $T$ — the number of test cases.
Each test case consists of:

One line with four integers $H, W, N, L$ — the room’s height, width, the number of sunspots, and the time horizon.
$N$ following lines, each with five decimal numbers $x_{i}^{(0)}, y_{i}^{(0)}, v_{x, i}, v_{y, i}, R_{i}$ describing the initial center, velocity, and radius of the $i$ -th sunspot.

All coordinates, velocities, and radii are given in the same units; time is in seconds.

Output

For each test case, output a line in the form Case #i: ans, where ans is the total length of time within $[0, L]$ when escape is possible (i.e., when there exists a safe vertical). Answers are real numbers; your output will be accepted if it has an absolute or relative error of at most $1 0^{- 9}$ .

Constraints

$2 \leq H, W \leq 1000$
$1 \leq N \leq 100$
$1 \leq L \leq 2000$
$- 2000.0 \leq v_{x, i}, v_{y, i} \leq 2000.0$
$- 2000.0 \leq x_{i}^{(0)} \leq W + 2000.0$
$- 2000.0 \leq y_{i}^{(0)} \leq H + 2000.0$
$0.0 < R_{i} \leq 1000.0$

All decimal numbers will have at most 3 digits after the decimal point.

Sunspots may start outside the room or move outside it during $[0, L]$ .

Example

Input

3
8 6 2 10
0 1 0.5 0 2
5 6 -1 0 2
8 6 2 10
0 1 1 0 2
5 6 0.01 0 2
8 6 2 10
1 1 0.4 0 2
5 6 -0.4 0 2

Output

Case #1: 9.666666666667
Case #2: 9.010101010101
Case #3: 5.0

Explanation

Case 1. The sunspots at $t = 0$ look as follows:

sample1

At $t = 0.666 (6)$ , the two sunspots will fully cover the horizontal space, until at $t = 1.0$ , the second sunspot moves away from the right wall, after which the vampire can always find a vertical line to the top.

Case 2. This time, the first sunspot is moving faster, whereas the second sunspot is moving incredibly slowly, and also to the right. At time $t = 1.0101 (01)$ , the first sunspot will "catch up" to the second sunspot:

sample2

At time $t = 2.0$ , the first sunspot will move away from the left wall, and the vampire is able to cross to the top again after that moment.

Case 3. This time, the two sunspots initially fully cover the horizontal space, but at time $t = 2.5$ they move away from the walls, until at time $t = 7.5$ each of them touches the opposite wall again.