Background

Fourier has been promoted to the Minister of Transportation for Paris. Eager to make his mark, he has decided to restructure the city's transportation system.

Description

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

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

In regions without conveyor belts, the $y$-coordinate is not affected by any belt.

In addition to the movement provided by the conveyor belts, a person can move on their own. To avoid tripping when moving between conveyor belts with different speeds, Fourier commissioned Maxwell to design shoes with steel plates on the soles and installed powerful magnets on the belts. With these shoes, you can only move along a direction parallel to one of the coordinate axes, potentially in the same or opposite direction as the axis, at a speed not exceeding $V$ units per second. With these shoes, when moving from one conveyor belt to another, the previous velocity is not inherited; the person immediately moves according to the speed of the new conveyor belt. (Naturally, one's own movement can still be performed simultaneously.)

The movement of the person and the movement of the conveyor belts are additive.

At any moment, the person can freely adjust their speed and direction of movement; they can achieve an approximate diagonal movement by continuously switching directions at extremely small intervals, or even dynamically adjust speed and direction to achieve approximate curved motion; however, at any instant, their speed must be parallel to a coordinate axis and have a magnitude not exceeding $V$.

Even in locations without conveyor belts, the person can still move by their own free will, but they are still restricted to moving along the coordinate axes at a speed not exceeding $V$ units per second. (The reason is that Maxwell's boots have become legendary equipment.)

Now, Fourier wants to know how great his transportation system is. Therefore, he has posed $q$ queries to you. For each query, if a person wants to travel from $(x_1, y_1)$ to $(x_2, y_2)$, what is the minimum time required? Since Fourier is the only true god, he would certainly not design a flawed transportation system, so all $v_i$ are strictly less than $V$, ensuring that it is always possible to walk from one location to another. (Although this means that even in the optimal case, the time to reach the destination via the conveyor system cannot be less than half of the original time, and more often it is slower, but he is the Minister of Transportation, and you are just his employee.)

Input

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

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 next $q$ lines each contain four integers $x_1, y_1, x_2, y_2$, representing the starting and ending points of the query.

Output

For each query, output a single real number representing the minimum time required for the movement, in seconds. You must ensure that the relative or absolute error of your output compared to the standard answer does not exceed $10^{-5}$.

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

Examples

Input 1

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

Output 1

4.3333333333
6.5

Note 1

In the first query, the image above shows an optimal way of walking. The blue area is the region where the conveyor belt is located. While on it, we move at a speed of $(3, 12)$ per second (where the self-movement speed is $(3, 7)$, which can be seen as moving in the positive $x$ direction for 30% of the time and in the positive $y$ direction for 70% of the time; by continuously switching in extremely short intervals, one can achieve the diagonal movement shown in the figure above; the self-movement of $(3, 7)$ is added to the conveyor belt's movement of $(0, 5)$ to result in a velocity vector of $(3, 12)$).

In the second query, the image above shows an optimal walking plan.

Note that for both queries, there is more than one optimal walking plan.

Input 2

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

Output 2

2
2
7.6666666667
10

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

Output 3

8.085714
1.815789
2.382353
4.987500
3.988235

Constraints

For all data, $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$, and $0 \leq |v_i| < V \leq 5 \times 10^5$.

• Subtask 1 (5%): $n = 0$.
• Subtask 2 (10%): $n, q \leq 1000$.
• Subtask 3 (10%): For all queries, $x_1 = p_0, x_2 = p_n$.
• Subtask 4 (10%): All queries have the same $x_1$ and the same $x_2$ (but $x_1 = x_2$ is not guaranteed).
• Subtask 5 (15%): $v_i$ is monotonically non-decreasing, and for all queries $x_1 \leq x_2$.
• Subtask 6 (15%): There exists an $i$ such that $p_i = x_1 = x_2$ (but it is not guaranteed that $i$ is the same for all queries).
• Subtask 7 (15%): Except for $n, q, V$, other values are independently and randomly generated within the valid range ($p$ is generated by picking $n+1$ distinct values in $[-5 \times 10^5, 5 \times 10^5]$ and sorting them).
• Subtask 8 (10%): $n, q \leq 5 \times 10^4$.
• Subtask 9 (10%): No special restrictions.