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)$.
$1 <= T <= 100$
$1 <= N <= 1000$
$1 <= W, H <= 10^6$
$1 <= Q <= 5 times 10^5$
$0 <= x_1 < x_2 <= W$
$1 <= y < H$
For $90 %$ test cases: $N <= 100$, $Q <= 1000$
## Input
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)$.
## Output
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)$.
[samples]
## Note
$1 <= T <= 100$$1 <= N <= 1000$$1 <= W, H <= 10^6$$1 <= Q <= 5 times 10^5$$0 <= x_1 < x_2 <= W$$1 <= y < H$For $90 %$ test cases: $N <= 100$, $Q <= 1000$
**Definitions**
Let $ N, M, I \in \mathbb{Z}^+ $ denote the number of rows, columns, and intervals, respectively.
Let $ G \in \{ \text{`.`}, \text{`#`}, \text{`*`}, \text{`a`}, \dots, \text{`z`} \}^{N \times M} $ be the grid representing the auditorium, where:
- `.` = empty floor (no chair),
- `#` = empty chair,
- `*` = outlet,
- `a`–`z` = competitor from a unique team.
Let $ C \subseteq \{ (i,j) \in [N] \times [M] \mid G[i][j] \in \text{`a`–`z`} \} $ be the set of occupied positions.
For each position $ (i,j) \in C $, let $ t(i,j) \in \text{`a`–`z`} $ denote the team of the competitor at $ (i,j) $.
Let $ D = \{ (0,-1), (-1,0), (1,0), (0,1) \} $ be the set of four adjacent directions: west, north, south, east (in priority order).
For any cell $ (i,j) $, define the **taxicab distance** to the nearest outlet as:
$$
d(i,j) = \min_{(x,y) \in G^{-1}(\text{`*`})} (|i - x| + |j - y|)
$$
A chair at $ (i,j) $ is **accessible** iff $ d(i,j) \leq 3 $.
A chair at $ (i,j) $ is **safe** iff no adjacent cell (in $ D $) contains a competitor from a different team.
**Constraints**
1. $ 1 \leq N, M, I \leq 100 $
2. Each team is uniquely identified by a lowercase letter.
3. Competitors move only to adjacent empty chairs (`#`) that are accessible, safe, and most preferred.
4. Conflicting moves (two or more competitors targeting the same chair) result in no movement for all involved.
**Objective**
Simulate $ I $ iterations of seat-hopping:
For each iteration:
1. For each competitor at $ (i,j) $, determine the set $ V(i,j) \subseteq D $ of valid adjacent empty chairs (`#`) that are accessible and safe.
2. From $ V(i,j) $, select the highest-priority direction (in order: north, west, east, south) yielding a valid target $ (i',j') $.
3. For each target cell $ (i',j') $, if exactly one competitor attempts to move into it, then move that competitor; otherwise, no one moves.
4. Update grid: vacate original positions, occupy new positions.
Output the grid $ G $ after $ I $ iterations.