Efficient Navigation on Moving Sidewalks

Consider an infinite 2D plane representing the map of Paris. Fourier has constructed n moving sidewalks. The i-th moving sidewalk is installed in the vertical strip where \(x\in [p_{i-1},p_i)\) and \(y\in \mathbb{R}\). Outside the range \(x<p_0\) or \(x\ge p_n\), no moving sidewalk is built.

When a person is in the region of the i-th sidewalk, they are forced to move in the positive \(y\) direction at speed \(v_i\) (if \(v_i\) is negative, then their \(y\) coordinate decreases at speed \(|v_i|\)). When not on any moving sidewalk, the \(y\) coordinate is unaffected by any automatic movement.

In addition to the motion induced by the sidewalks, the person can move by themselves. To avoid accidents when switching between sidewalks of different speeds, Maxwell has designed special boots. With these boots, the person is only allowed to move parallel to one of the coordinate axes (either in the same or opposite direction) with an instantaneous speed not exceeding \(V\) units per second. Moreover, when moving from one sidewalk to another, any previous personal vertical or horizontal movement is discarded – the new sidewalk's automatic velocity instantly takes effect (of course, personal movement can be combined simultaneously).

The key point is that the person's own movement and the sidewalk's motion are added together.

At any moment, the person can freely change their movement rate and direction; by switching between the two allowed axes in arbitrarily small intervals they can even approximate diagonal or curved motion. However, at every instant the personal speed is limited to be at most \(V\) in the direction that is parallel to one of the coordinate axes. (Even off the sidewalks, the person’s movement is subject to the same restriction.)

Fourier now wonders how great his transportation system really is. He poses q queries: 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? Fourier has ensured that \(|v_i|<V\) for all \(i\), so it is always possible to travel between any two points.

Explanation: While moving horizontally, the person must use their own effort since the sidewalks do not contribute in the \(x\)-direction. Thus, the minimum horizontal time is \(\frac{|x_2-x_1|}{V}\). For the vertical direction, when the person is in a sidewalk region with interval \([p_{i-1},p_i)\), the sidewalk automatically adds a vertical speed of \(v_i\) (which may be negative) to the person’s own vertical movement. In the absence of any sidewalk (or if the sidewalk’s contribution is not in the desired direction), the person can move vertically using a personal speed up to \(V\) (by dedicating time solely for vertical movement). Because one may plan the journey arbitrarily (even using arbitrarily short intervals of switching directions to approximate simultaneous horizontal and vertical motion), a strategy that goes directly from \((x_1,y_1)\) to \((x_2,y_2)\) is always valid. In this direct route the person spends exactly \(\frac{|x_2-x_1|}{V}\) seconds covering the horizontal displacement, and, while traversing the horizontal interval \([\min(x_1,x_2),\max(x_1,x_2)]\), automatically benefits from any moving sidewalk that lies in that interval. In particular, if \(y_2-y_1\) is positive then any sidewalk with \(v_i>0\) adds extra vertical displacement, computed as the product of \(v_i\) and the time spent in that sidewalk. (Similarly, when \(y_2-y_1\) is negative, only sidewalks with \(v_i<0\) are beneficial.)

This leads to the following optimal strategy: take the direct horizontal path from \(x_1\) to \(x_2\) (which takes \(\frac{|x_2-x_1|}{V}\) seconds) and, along that interval, accumulate a bonus vertical displacement from the sidewalks. Let the overlap length of the direct horizontal segment with the \(i\)-th sidewalk be \(L_i=\max(0,\min(\max(x_1,x_2),p_i)-\max(\min(x_1,x_2),p_{i-1}))\). Then, if \(y_2-y_1\) is positive, the bonus is \(\sum_{i:v_i>0} v_i\frac{L_i}{V}\); if negative, the bonus is \(\sum_{i:v_i<0} |v_i|\frac{L_i}{V}\). The remaining vertical displacement that must be provided by personal movement is \(\max(0,|y_2-y_1|-\text{bonus})\), which takes \(\frac{\max(0,|y_2-y_1|-\text{bonus})}{V}\) seconds. Therefore, the minimum required time is given by

[ T=\frac{|x_2-x_1|}{V}+\frac{\max(0,|y_2-y_1|-\text{bonus})}{V}. ]

Your task is to answer all the queries.

inputFormat

The input begins with a line containing two integers \(n\) and \(V\) (the number of moving sidewalks and the maximum personal speed). The next line contains \(n+1\) real numbers \(p_0, p_1, \dots, p_n\) (with \(p_0 < p_1 < \cdots < p_n\)) describing the boundaries of the moving sidewalks. The following line contains \(n\) real numbers \(v_1, v_2, \dots, v_n\) representing the vertical speeds of the sidewalks. Next, an integer \(q\) is given, representing the number of queries. Each of the following \(q\) lines contains four real numbers \(x_1, y_1, x_2, y_2\) representing a query.

Note: All \(v_i\) satisfy \(|v_i|<V\).

outputFormat

For each query, output the minimum required time to go from \((x_1, y_1)\) to \((x_2, y_2)\). It is recommended to output the answer as a floating‐point number with at least 6 digits of precision.

sample

1 5
2 6
2
1
0 0 10 10

3.680000