Problem N
Never Give Up

I will never give up. I will never go back on my word. That is my Ninja Way!!

Your best friend, after the brutal murder of his entire clan by none other than his own brother, decided to leave the village to learn from the dark lord to exert his vengeance. Unwilling to see him go down this dark path, you decided to stop him and bring him back by force if you must. Unfortunately, in your final confrontation, you were defeated by his rage.

“I will never give up. I will definitely bring you back!” you screamed. Lord Pooty, the strongest and wisest of them all, was touched by your efforts and decided to train you. Here is your first lesson!

The first lesson is on accuracy. You are sent to a cave with many ridges and your goal is to throw your kunai such that it does not hit any of the ridges. Let us elaborate.

The cave is $w$ meters long and $h$ meters tall, and is defined by the top wall and the bottom wall. Both walls have ridges sticking out, defined in the following way.

• On the bottom wall, there are $n_ b$ points $p_ i$, where $p_1 = (0,0)$ and $p_{n_ b} = (w,0)$. We connect $p_ i$ and $p_{i+1}$ with a straight line segment for all $1 \leq i \leq n_ b-1$.

• On the top wall, there are $n_ t$ points $q_ i$, where $q_1 = (0,h)$ and $q_{n_ t} = (w,h)$. We connect $q_ i$ and $q_{i+1}$ with a straight line segment for all $1 \leq i \leq n_ t-1$.

In other words, the ridges on the top and bottom wall form polygons defined by the points $\{ p_ i\} $ and $\{ q_ i\} $. Some polygons may intersect with each other.

You will throw the kunai straight horizontally from $(0, k)$ with a starting speed $v$ (meters per second). For simplicity, your kunai can be represented by a single point, and its trajectory will follow the law of physics with $g = 10$ (meters per second squared). In case you forget basic physics, the parametric formulas for $x(t)$ and $y(t)$ — the $x$ and $y$ coordinate of the kunai at time $t$ (seconds) — are as follows.

Unfortunately, you are not very good at controlling your throwing speed. As such, $v$ will be a random real number uniformly distributed from the range $[L,R]$. You want to compute the probability of your throw being successful; i.e., your kunai does not hit or touch the ridges on the top and bottom wall.

Input

The input starts with a line containing an integer $C$, denoting the number of test cases ($1 \leq C \leq 10\, 000$). Each test case has the following input format.

The first line contains four integers: $w$, $h$, $n_ b$, and $n_ t$, denoting the width of the cave, the height of the cave, the number of points defining the ridges on the bottom wall, and the number of points defining the ridges on the top wall, respectively ($1 \leq w, h \leq 10^9$; $2 \leq n_ t, n_ b \leq \min (w + 1, 100\, 000)$).

The second line describes the bottom wall and contains $n_ b$ pairs of two integers $(x_ i, y_ i)$, denoting the points $p_ i$ ($0 = x_1 < x_2 < \cdots < x_{n_ b} = w$; $0 \leq y_ i \leq h$; $p_1 = (0, 0)$; $p_{n_ b} = (w, 0)$). The sum of $n_ b$ across all test cases does not exceed $100\, 000$.

The third line describes the top wall and contains $n_ t$ pairs of two integers $(x_ i, y_ i)$, denoting the points $q_ i$ ($0 = x_1 < x_2 < \cdots < x_{n_ t} = w$; $0 \leq y_ i \leq h$; $q_1 = (0, h)$; $q_{n_ t} = (w, h)$). The sum of $n_ t$ across all test cases does not exceed $100\, 000$.

The fourth line contains three integers $k$, $L$, and $R$, denoting the height you made your throw and the lower bound and upper bound of the speed you can throw your kunai ($1 \leq k \leq h-1$; $1 \leq L < R \leq 10^9$).

Output

For each test case, output a single line containing a non-negative real number, denoting the probability of your throw succeeding. Your answer is considered correct if the absolute error of each value is at most $10^{-5}$. In other words, if the correct value is $x$ and your answer is $y$, then $|x - y| \leq 10^{-5}$.

Explanation of Sample Input

For the first test case, if you throw your kunai at speed $v=13$, the following is what the trajectory looks like. The throw is successful since it does not hit any ridges.

However, if you throw your kunai at speed $v=16$, the following is what the trajectory looks like. The throw is not successful since it hits the ridges on the top wall.

5
10 10 3 3
0 0 5 6 10 0
0 10 9 5 10 10
7 1 100
10 10 3 3
0 0 5 6 10 0
0 10 9 5 10 10
9 1 100
10 10 3 3
0 0 5 10 10 0
0 10 5 0 10 10
5 1 100
919300 946 6 2
0 0 752 2 24461 0 510156 0 836493 1 919300 0
0 946 919300 946
708 1 846
919300 946 6 2
0 0 752 2 24461 0 510156 0 836493 1 919300 0
0 946 919300 946
708 70000 80000

0.0308071675
0.0060230787
0
0
0.2745171379