Bell (Bell)

JOI City has one road that is long enough to be treated as a number line. Each point on the road is given by a single real coordinate.

Along this road, JOI City has $N$ bells, numbered from $1$ to $N$ in increasing order of coordinate. Bell $i$ ($1 \le i \le N$) is at coordinate $A_i$.

At the end of each year, JOI City rings all of these bells at once. This is a major event for the city.

When a bell is rung, it sounds with strength $K$ at its own location. The strength drops by $1$ for every unit of distance from the bell, and it becomes $0$ at distance $K$ or more. So when bell $i$ is rung, the strength of its sound at coordinate $x$ is $\max\{K-|x-A_i|,0\}$, where $|t|$ is the absolute value of $t$.

When all the bells are rung, the strength of the bell sound at coordinate $x$ is the maximum of the sound strengths that each bell produces at $x$.

JOI City has $M$ houses along this road, numbered from $1$ to $M$ in order of age, with the oldest first. House $j$ ($1 \le j \le M$) is at coordinate $B_j$.

As the mayor of JOI City, you want to know the strength of the bell sound heard at each house when all the bells are rung.

Given the bell and house information for JOI City, write a program that computes the strength of the bell sound heard at coordinates $B_1, B_2, \ldots, B_M$ when all the bells are rung.

The input is given in the following format.

N M K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output $M$ lines. On line $j$ ($1 \le j \le M$), print the strength of the bell sound heard at coordinate $B_j$ when all the bells are rung.

• $1 \le N \le 250000$.
• $1 \le M \le 250000$.
• $1 \le K \le 10^9$.
• $0 \le A_i \le 10^9$ ($1 \le i \le N$).
• $A_i < A_{i+1}$ ($1 \le i \le N-1$).
• $0 \le B_j \le 10^9$ ($1 \le j \le M$).
• $B_j \ne B_k$ ($1 \le j < k \le M$).
• All input values are integers.