Background

Fourier has been promoted to the Minister of Transportation of Paris. As a new official eager to make changes, Fourier decides to rebuild Paris’s transportation system.

Problem Description

The map of Paris can be viewed as an infinite 2D plane. Fourier has built $n$ conveyor belts on it: the $i$-th conveyor belt is built in the region $x\in[p_{i-1},p_i),y\in\mathbb R$. For the parts with $x<p_0$ or $x\geq p_n$, Fourier did not build any conveyor belt.

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

When staying in a region without a conveyor belt, the $y$ coordinate is not affected by any conveyor belt.

Besides being carried by the conveyor belt, the person can also move by themself. To avoid falling accidents when moving between conveyor belts with different speeds, Fourier asked Maxwell to design shoes with steel plates on the soles, and installed strong magnets on the conveyor belts. After wearing such shoes, you can only move along a direction parallel to one of the coordinate axes, possibly in the same or opposite direction, at a speed of at most $V$ units per second. With these shoes, when moving from one conveyor belt to another, the previous belt speed is not inherited; the person immediately starts moving according to the new belt’s speed (of course, the person’s own movement can still happen at the same time).

The person’s own motion and the conveyor belt’s motion are added together.

At any moment, the person may freely adjust their movement speed and direction. They may switch directions repeatedly within extremely small time intervals to achieve an approximately diagonal movement effect, and may even adjust speed and direction dynamically to achieve an approximately curved trajectory. However, at any moment, the instantaneous velocity must be parallel to a coordinate axis and have magnitude at most $V$.

Even at positions without a conveyor belt, the person can still move by free will, but still only along coordinate-axis directions at a speed of at most $V$ units per second (because Maxwell’s boots have become “concept-level equipment”).

Now Fourier wants to know how great his transportation system really is. Therefore, he asks you $q$ queries. In each query, if a person wants to go from $(x_1,y_1)$ to $(x_2,y_2)$, what is the minimum time required. Since Fourier is the one true god, he would of course not design a flawed transportation system, so the absolute values of all $v_i$ are strictly less than $V$, and thus it is always possible to travel from one position to another. (Although this implies that even in the optimal case, using the conveyor-belt system cannot make the travel time less than half of the original, and more often it is actually slower. But he is the Minister of Transportation, and you are just an employee under him.)

Input Format

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

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

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

Then follow $q$ lines. Each line contains four integers $x_1,y_1,x_2,y_2$, representing the start and end points of the query.

Output Format

For each query, output one real number per line, representing the minimum time needed for this movement, in seconds. You need to ensure that the relative or absolute error compared to the standard answer does not exceed $10^{-5}$.

• If you suspect that there is a large precision error in your code, you may try to use more integers and fractions to avoid floating-point operations, thereby reducing errors.

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

4.3333333333
6.5

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

2
2
7.6666666667
10

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

8.085714
1.815789
2.382353
4.987500
3.988235

Hint

For Samples #4 and #5, see the attachment.

Explanation for Sample #1:

In the first query, the figure above shows a near-optimal way of walking. The blue area is the region with a conveyor belt; while on it, we move at a speed of $(3,12)$ per second (where the person’s own movement speed is $(3,7)$, meaning that it can be seen as spending 30% of the time moving along the positive $x$-axis direction and 70% of the time moving along the positive $y$-axis direction. By switching continuously within extremely short time intervals, you can achieve the diagonal movement shown in the figure. The person’s own walking $(3,7)$ and the conveyor belt’s operation $(0,5)$ add up to the velocity vector $(3,12)$).

In the second query, the figure above shows a near-optimal walking plan.

Note that, in these two queries, the walking plan that achieves the minimum time is not unique; there are more than the two shown in the figures.

For all testdata, it holds that $n,q\leq1.5\times10^5$, $-5\times10^5\leq p_0<p_1<p_2<\dots<p_n\leq5\times10^5$, $|x_1|,|y_1|,|x_2|,|y_2|\leq5\times10^5$, $0\leq|v_i|<V\leq5\times10^5$.

• Subtask 1 (5 points): Guarantee $n=0$.
• Subtask 2 (10 points): Guarantee $n,q\leq1000$.
• Subtask 3 (10 points): Guarantee that for all queries, $x_1=p_0,x_2=p_n$.
• Subtask 4 (10 points): Guarantee that all queries have the same $x_1$, and all queries have the same $x_2$ (but not necessarily $x_1=x_2$).
• Subtask 5 (15 points): Guarantee that $v_i$ is non-decreasing, and the queries satisfy $x_1\leq x_2$.
• Subtask 6 (15 points): Guarantee that there exists an $i$ such that $p_i=x_1=x_2$. (But it is not guaranteed that all queries share the same $i$.)
• Subtask 7 (15 points): Guarantee that except for $n,q,V$, all other values are obtained independently at random within the valid range (the random method for $p$ is to randomly pick $n+1$ distinct values from $[-5\times10^5,5\times10^5]$ and sort them).
• Subtask 8 (15 points): Guarantee $n,q\leq5\times10^4$.
• Subtask 9 (10 points): No special constraints.

Translated by ChatGPT 5