Snow Clearing with Battery Constraints

A road of length \(l\) meters (represented by the interval \([0,l]\) on the number line) is blanketed with snow every day. There are \(n\) charging stations located along the road. A snow‐clearing machine is used to remove the snow. The machine has the following properties:

• It moves at a constant speed of 1 meter per second.
• It can clear snow only while moving; moving without clearing costs 1 second per meter and does not consume battery.
• When moving while clearing snow the machine sweeps snow at the same time. In this mode the battery is consumed at a rate of \(1/k\) per meter (so a full charge lets the machine clear at most \(k\) meters of road).
• Charging is instantaneous (takes no time) but can only be done at a working charging station.

Initially, the machine has no charge. On each day the following information is given:

1. The road parameters \(l, n, k\).
2. A list of the positions of the \(n\) charging stations.
3. A daily query consisting of a starting position of the machine (anywhere on \([0,l]\)) and the working statuses of the \(n\) charging stations (each status is either 1 meaning working or 0 meaning broken). It is guaranteed that at least one charging station is working so that clearing all snow is possible.

The machine must remove snow from the entire road \([0,l]\). Note that the machine can move without sweeping snow (and thus without battery consumption) if desired; however, snow is removed only when the machine is in the sweeping mode (i.e. moving while clearing snow), and each such movement consumes battery. Also note that the battery can only cover at most \(k\) meters of snow clearance per charge. Therefore, the machine must plan its route so that every section of the road is swept under the battery constraint, and it can recharge as many times as needed at working charging stations.

Important observation

Once the machine is charged at a charging station, it can clear at most \(k\) consecutive meters before the battery is depleted. Hence, the continuous segments that are swept must be of length at most \(k\). The standard strategy on a line is to first get charged at a working station and then plan a route that sweeps the entire interval \([0,l]\) with the minimal travel distance. It turns out that if the machine starts its sweeping route from a working station at position \(x\) (after incurring an initial travel cost of \(|s-x|\) to reach that station starting from \(s\)), the minimal additional time (distance) needed to clear the whole road is

[ T(x)=l+\min{x,l-x} ]

(The machine can sweep by first going to one end and then reversing direction towards the other end.) Thus, the minimum total time is

[ \min_{x\in W}\Big{|s-x|+l+\min{x,l-x}\Big}, ]

where \(W\) is the set of positions of working charging stations. (The feasibility of sweeping under the battery constraint is guaranteed by the input conditions.)

Input/Output Format

inputFormat

The input begins with a line containing three integers \(l\), \(n\), and \(k\) \((1 \leq l, k \leq 10^9,\ 1 \leq n \leq 10^5)\) representing the road length, the number of charging stations, and the clearing distance per full charge respectively.

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\) \((0 < p_i < l)\) representing the positions of the charging stations (not necessarily sorted).

The third line contains a single integer \(t\) \((1 \leq t \leq 10^5)\), the number of days (queries).

Then for each day there are two lines:

• The first line contains an integer \(s\) \((0 \leq s \leq l)\) representing the machine's initial position (note: the machine starts with no charge).
• The second line contains \(n\) integers, each either 0 or 1. The \(i\)th integer indicates whether the charging station at position \(p_i\) is working (1) or broken (0) on that day.

It is guaranteed that in each query at least one charging station is working and that the working stations allow a feasible solution (i.e. the gaps between consecutive working stations or between an endpoint and the nearest working station do not exceed \(k\)).

outputFormat

For each day, output a single integer: the minimum time (in seconds) required to clear all the snow along the road \([0,l]\).

sample

10 3 5
2 5 9
3
5
1 1 1
0
1 0 1
10
0 1 1

15
14
12

</p>