M. Minimize Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ where $$$|a_i| = 1$$$ for each index $$$i$$$ $$$(1 \le i \le n)$$$, and two integers $$$l$$$ and $$$r$$$ $$$(l \le r)$$$.

We have a real-valued function $$$f$$$ defined as follows:

$$$$$$f(x) = \sum_{i=1}^{n} |a_i \cdot x + b_i|.$$$$$$

Suppose we randomly pick a real value $$$m$$$ in the range $$$(l \le m \le r)$$$. What is the probability that $$$f(m)$$$ equals the minimum value of $$$f$$$ in the given range $$$[l, r]$$$. More formally,

$$$$$$f(m) = \displaystyle\min_{l \le x \le r} f(x).$$$$$$

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n, l, r$$$ $$$(1 \le n \le 2 \cdot 10^5, -10^9 \le l \le r \le 10^9)$$$ — the length of the array $$$a$$$, and the endpoints of the given range.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(|a_i| = 1)$$$ — the elements of the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(-10^9 \le b_i \le 10^9)$$$ — the elements of the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the probability that $$$f(m)$$$ equals the minimum value of $$$f$$$ in the given range $$$[l, r]$$$. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.

Formally, let your answer be $$$p$$$, and the jury's answer be $$$q$$$. Your answer is considered correct if and only if $$$\dfrac{|p - q|}{\max(1, |q|)} \le 10^{-9}$$$.

Example
Input
3
1 2 2
-1
3
1 2 4
-1
3
2 3 5
1 1
-2 -4
Output
1.0000000000
0.0000000000
0.5000000000
Note

For the first test case, there is only one possible value for $$$m$$$ which satisfies $$$f(m) = \displaystyle\min_{2 \le x \le 2} f(x) = 1$$$, and it is $$$2$$$. Thus, the probability of randomly picking $$$2$$$ in the range $$$[2, 2]$$$ is $$$1$$$.

For the second test case, there is only one possible value for $$$m$$$ which satisfies $$$f(m) = \displaystyle\min_{2 \le x \le 4} f(x) = 0$$$, and it is $$$3$$$. Thus, the probability of randomly picking $$$3$$$ in the range $$$[2, 4]$$$ is $$$0$$$.

For the third test case, there is a range of possible values for $$$m$$$ which satisfies $$$f(m) = \displaystyle\min_{3 \le x \le 5} f(x) = 2$$$, and it is $$$[3, 4]$$$. Thus, if we randomly pick a value in the range $$$[3, 5]$$$, the probability that it lies in the range $$$[3, 4]$$$ is $$$\dfrac{1}{2} = 0.5$$$.