Existem $N$ postes de iluminação acesos em uma estrada representada por uma reta numérica. Suas posições, da esquerda para a direita, são $A_1<\cdots<A_N$.
Defina a escuridão na posição $x$ como a distância dessa posição ao poste de iluminação mais próximo. Ela é o mínimo dos $N$ números $|A_1-x|,\ldots,|A_N-x|$. Aqui, $|\cdot|$ indica valor absoluto: $|y|:=y$ se $y\ge0$, e $|y|:=-y$ se $y<0$.
Por exemplo, se $N=3$ postes estiverem em $A_1=1$, $A_2=4$ e $A_3=8$, a escuridão em cada posição inteira de $0$ a $10$ será a seguinte.
| Posição | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Escuridão | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $2$ | $1$ | $0$ | $1$ | $2$ |
| Há poste? | O | O | O |
Escreva um programa que calcule a escuridão nas $L+1$ posições inteiras de $x=0$ a $x=L$ e imprima os valores em ordem, do menor ao $K$-ésimo menor.
Restrições
- Todos os números dados são inteiros.
- $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$
Subtarefas
| # | Pontos | Condição |
|---|---|---|
| 1 | 10 | $N=1$ |
| 2 | 20 | $N\le2\,500$, $L\le2\,500$ |
| 3 | 15 | $2\le N$. $N-1$ divide $L$. $A_i=\frac{L}{N-1}\times(i-1)$. |
| 4 | 20 | $L\le5\,000\,000$ |
| 5 | 35 | Não há restrições adicionais. |
Entrada
A primeira linha contém três inteiros $L,N,K$, nessa ordem, separados por espaços.
A próxima linha contém $N$ inteiros $A_1,\ldots,A_N$, nessa ordem, separados por espaços.
Saída
Imprima a resposta em $K$ linhas, a partir da primeira. A linha $i$ deve conter o $i$-ésimo menor valor de escuridão.
Exemplos
Entrada 1
10 3 4 1 4 8
Saída 1
0 0 0 1
Entrada 2
4 5 5 0 1 2 3 4
Saída 2
0 0 0 0 0
Entrada 3
7 1 4 3
Saída 3
0 1 1 2
Entrada 4
9 4 10 0 3 6 9
Saída 4
0 0 0 0 1 1 1 1 1 1