There are $N$ lit streetlights on a road represented by a number line. Their positions, from left to right, are $A_1<\cdots<A_N$.
Define the darkness at position $x$ as the distance from that position to the nearest streetlight. This is the minimum of the $N$ numbers $|A_1-x|,\ldots,|A_N-x|$. Here $|\cdot|$ denotes absolute value: $|y|:=y$ for $y\ge0$, and $|y|:=-y$ for $y<0$.
For example, if $N=3$ streetlights are at $A_1=1$, $A_2=4$, and $A_3=8$, the darkness at each integer position from $0$ to $10$ is as follows.
| Position | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Darkness | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $2$ | $1$ | $0$ | $1$ | $2$ |
| Streetlight present? | O | O | O |
Write a program that computes the darkness at all $L+1$ integer positions from $x=0$ to $x=L$ and prints the values in order from the smallest through the $K$-th smallest.
Constraints
- All given numbers are integers.
- $1\le L\le 1\,000\,000\,000\,000\,000\,000$
- $1\le N\le300\,000$
- $1\le K\le500\,000$
- $K\le L+1$
- $0\le A_1<A_2<\cdots<A_N\le L$
Subtasks
| # | Points | Condition |
|---|---|---|
| 1 | 10 | $N=1$ |
| 2 | 20 | $N\le2\,500$, $L\le2\,500$ |
| 3 | 15 | $2\le N$. $N-1$ divides $L$. $A_i=\frac{L}{N-1}\times(i-1)$. |
| 4 | 20 | $L\le5\,000\,000$ |
| 5 | 35 | There are no additional constraints. |
Input
The first line contains three integers $L,N,K$, in that order, separated by spaces.
The next line contains $N$ integers $A_1,\ldots,A_N$, in that order, separated by spaces.
Output
Print the answer on $K$ lines starting with the first line. The $i$-th line must contain the $i$-th smallest darkness value.
Examples
Input 1
10 3 4 1 4 8
Output 1
0 0 0 1
Input 2
4 5 5 0 1 2 3 4
Output 2
0 0 0 0 0
Input 3
7 1 4 3
Output 3
0 1 1 2
Input 4
9 4 10 0 3 6 9
Output 4
0 0 0 0 1 1 1 1 1 1