Street Lamps

A number line road has $N$ street lamps that are on. Listing their positions from left to right gives $A_1 < \cdots < A_N$.

The darkness of a position $x$ is defined as the distance from $x$ to the nearest lamp. This equals the smallest value among $|A_1 - x|, \cdots, |A_N - x|$, where $|\cdot|$ is the absolute value, so $|y| := y$ if $y \ge 0$ and $|y| := -y$ if $y < 0$.

For example, suppose $N = 3$ and the lamps are at $A_1 = 1$, $A_2 = 4$, and $A_3 = 8$. The darkness of each integer position from 0 to 10 is shown below.

Compute the darkness of all $L+1$ integer positions from $x = 0$ to $x = L$. Output the $K$ smallest values in increasing order.

The first line contains three integers $L$, $N$, and $K$, separated by spaces.

The second line contains $N$ integers $A_1, \cdots, A_N$, separated by spaces.

Print $K$ lines. The $i$-th line contains the $i$-th smallest darkness value.

• $1 \le L \le 10^{18}$
• $1 \le N \le 300{,}000$
• $1 \le K \le 500{,}000$
• $K \le L + 1$
• $0 \le A_1 < A_2 < \cdots < A_N \le L$
• All given numbers are integers.