Circus

A new circus act uses very long ropes that hang from the flat ceiling of the circus hall. The entrance of the hall and all the ropes lie on one straight line. The ceiling is $10^{18}$ units high, and every rope hangs freely down to the ground. The performer moves from rope to rope and has to get at least $M$ units away from the entrance.

There are $N$ ropes. Rope $i$ hangs at the point that is $P_i$ units from the entrance, measured along the ceiling.

The performer is careful and never jumps wildly. Suppose she holds rope $i$ at a point $S$ units below the ceiling. She can swing on the rope she is holding. If she reaches a point at least $M$ units from the entrance while swinging, her task is done. While swinging she can grab another rope that hangs at most $S$ units away from the rope she holds. Formally, she can grab rope $j$ if $|P_i - P_j| \le S$. She now holds rope $i$ and rope $j$ at the same time. From there she climbs rope $i$ while keeping rope $j$ in her hands. Once she reaches the point where rope $i$ touches the ceiling, rope $j$ is pulled tight along the ceiling. From that moment she continues her movement holding rope $j$ at a point $|P_i - P_j|$ units below the ceiling.

The manager wants to hang one more rope, a temporary one, at the point that is $D$ units from the entrance along the ceiling. The act starts on that rope. The performer has to travel from it to the far end of the hall, at least $M$ units from the entrance. While she moves from rope to rope, the temporary rope behaves exactly like a regular rope. Write a program that computes the smallest distance below the ceiling at which the performer must hold the temporary rope so that she can finish her task.

Consider three ropes hanging 0, 3 and 6 units from the entrance, with the target $M = 8$. The temporary rope is 4 units from the entrance. If the performer holds the temporary rope (drawn bold) 3 units below the ceiling, she can swing and grab the rope that is 6 units from the entrance. After grabbing it she climbs the temporary rope to the ceiling, and she then holds the rope at 6 at a point $6 - 4 = 2$ units below the ceiling. Swinging again from there, she reaches the target point 8 units from the entrance.

The manager has several candidate places for the temporary rope and wants the answer for each of them.

The first line contains the number of ropes $N$ and the target distance $M$, separated by a space.

Each of the next $N$ lines contains one rope position $P_i$.

The next line contains the number of queries $Q$.

Each of the last $Q$ lines contains one position $D$ of the temporary rope.

Print $Q$ lines, one answer per query, in the order the queries are given. Each line holds the smallest distance below the ceiling at which the performer must hold the temporary rope to finish her task.

• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le M \le 10^9$
• $0 \le P_i < M$
• $0 \le D < M$
• All numbers in the input are integers.
• Two different ropes may hang at the same position.

Take the ropes at 0, 3 and 6 with $M = 8$.

For a temporary rope at 4 the answer is 2. Holding it 2 units below the ceiling is enough, because $|4 - 6| = 2$ lets the performer grab the rope at 6; after climbing the temporary rope she holds the rope at 6 two units below the ceiling and reaches $6 + 2 = 8$. Another route runs from 4 to 0, then to 3, then to 6, and then to 8, but it forces her to hold the temporary rope 4 units below the ceiling at the start.

For a temporary rope at 5 the answer is 3. Here she reaches the target straight from the temporary rope, without touching any other rope.