Background

Fourier has been promoted to the Minister of Transportation in Paris. As a new leader, he is determined to overhaul the city's transportation system.

Problem Description

The map of Paris can be considered as an infinite two-dimensional plane. Fourier has constructed $n$ conveyor belts: the $i$-th conveyor belt is built in the region where $x \in [p_{i-1}, p_i)$ and $y \in \mathbb{R}$. For areas where $x < p_0$ or $x \geq p_n$, no conveyor belts have been constructed.

When a person is within the region of the $i$-th conveyor belt, they are forced to move at a speed of $v_i$ units per second in the direction of increasing $y$-coordinate. $v_i$ can be negative, in which case the $y$-coordinate decreases at the corresponding speed.

In areas without conveyor belts, the $y$-coordinate is not affected by the conveyor belts.

Apart from being influenced by the conveyor belts, the person can also move independently. To prevent accidents from transitioning between conveyor belts with different speeds, Fourier has commissioned Maxwell to design shoes with steel soles and installed powerful magnets on the conveyor belts. Wearing these shoes, one can only move parallel to one of the coordinate axes, in either direction, at a speed not exceeding $V$ units per second. With these shoes, when moving from one conveyor belt to another, the previous speed is not inherited; the person will immediately move according to the new conveyor belt's speed (naturally, independent movement can still occur simultaneously).

The individual's movement and the conveyor belt's movement are additive.

At any moment, the person can freely adjust their movement's speed and direction; by continuously switching directions in very short intervals, they can achieve an effect similar to diagonal movement, or even dynamically adjust speed and direction to achieve an effect similar to curved movement; however, their instantaneous speed at any moment can only be parallel to the coordinate axes and not exceed $V$.

Even in positions without conveyor belts, the person can still move by their own will, but only along the coordinate axes and at a speed not exceeding $V$ units per second (Maxwell's boots have become conceptual equipment).

Now, Fourier wants to know how great his transportation system is. Therefore, he asks you $q$ queries, each asking for the minimum time required for a person to travel from $(x_1, y_1)$ to $(x_2, y_2)$. Since Fourier is the only true god, he would never design a flawed transportation system, so the absolute values of all $v_i$ are strictly less than $V$, ensuring that one can always travel from one position to another. (Although this will result in the time to reach the destination through the conveyor belt system never being less than half the original time, and often being slower, but since he is the Minister of Transportation and you are just an employee under him, there's not much you can do about it.)

Input Format

The first line contains three integers $n$, $q$, and $V$, representing the number of conveyor belts, the number of queries, and the person's movement speed, respectively.

The next line contains $n+1$ integers $p_0, p_1, \dots, p_n$, representing the boundary information of the conveyor belts.

The next line contains $n$ integers $v_1, v_2, \dots, v_n$, representing the speed of each conveyor belt.

The following $q$ lines each contain four integers $x_1, y_1, x_2, y_2$, representing the start and end points of each query.

Output Format

For each query, output a single line containing a real number, representing the minimum time required for the movement, in seconds. Your output must ensure that the relative or absolute error does not exceed $10^{-5}$.

• If you suspect that your code has significant precision errors, you can try to avoid floating-point operations by using more integers and fractions, thereby reducing errors.

Sample Input and Output

Sample Input #1

1 2 10
-5 5
5
-10 -20 10 20
10 20 -10 -20

Sample Output #1

4.3333333333
6.5

Sample Input #2

1 4 10
-5 5
5
10 -10 10 10
10 10 10 -10
10 -50 10 50
10 50 10 -50

Sample Output #2

2
2
7.6666666667
10

Sample Input #3

5 5 10
-10 -5 0 5 10 15
9 -4 7 -6 2
-1 0 -9 -100
-7 0 7 10
9 0 -3 20
12 0 -17 -30
2 0 19 39

Sample Output #3

8.085714
1.815789
2.382353
4.987500
3.988235

Notes

Detailed explanations for Sample #4 and Sample #5 can be found in the attached files.

For all data, the following conditions are satisfied: $n, q \leq 1.5 \times 10^5$, $-5 \times 10^5 \leq p_0 < p_1 < p_2 < \dots < p_n \leq 5 \times 10^5$, $|x_1|, |y_1|, |x_2|, |y_2| \leq 5 \times 10^5$, $0 \leq |v_i| < V \leq 5 \times 10^5$.

• Subtask 1 (5 points): Guaranteed $n = 0$.
• Subtask 2 (10 points): Guaranteed $n, q \leq 1000$.
• Subtask 3 (10 points): Guaranteed for all queries, $x_1 = p_0, x_2 = p_n$.
• Subtask 4 (10 points): Guaranteed all queries have the same $x_1$, all queries have the same $x_2$ (but not guaranteed $x_1 = x_2$).
• Subtask 5 (15 points): Guaranteed $v_i$ is monotonically non-decreasing, and $x_1 \leq x_2$ for the queries.
• Subtask 6 (15 points): Guaranteed there exists an $i$ such that $p_i = x_1 = x_2$ (but not guaranteed all queries have the same $i$).
• Subtask 7 (15 points): Guaranteed except for $n, q, V$, other values are independently randomly generated within valid ranges (the random method for $p$ is to randomly select $n+1$ distinct values in $[-5 \times 10^5, 5 \times 10^5]$ and sort them).
• Subtask 8 (15 points): Guaranteed $n, q \leq 5 \times 10^4$.
• Subtask 9 (10 points): No special restrictions.

见题面 Input 部分

见题面 Output 部分