Il y a $N$ lampadaires allumés sur une route représentée par une droite numérique. Leurs positions, de gauche à droite, sont $A_1<\cdots<A_N$.
Définissons l’obscurité en position $x$ comme la distance entre cette position et le lampadaire le plus proche. C’est le minimum des $N$ nombres $|A_1-x|,\ldots,|A_N-x|$. Ici, $|\cdot|$ désigne la valeur absolue : $|y|:=y$ si $y\ge0$, et $|y|:=-y$ si $y<0$.
Par exemple, si $N=3$ lampadaires se trouvent en $A_1=1$, $A_2=4$ et $A_3=8$, l’obscurité en chaque position entière de $0$ à $10$ est la suivante.
| Position | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Obscurité | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $2$ | $1$ | $0$ | $1$ | $2$ |
| Lampadaire présent ? | O | O | O |
Écrivez un programme qui calcule l’obscurité aux $L+1$ positions entières de $x=0$ à $x=L$ et affiche les valeurs dans l’ordre, de la plus petite à la $K$-ième plus petite.
Contraintes
- Tous les nombres donnés sont entiers.
- $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$
Sous-tâches
| # | Points | Condition |
|---|---|---|
| 1 | 10 | $N=1$ |
| 2 | 20 | $N\le2\,500$, $L\le2\,500$ |
| 3 | 15 | $2\le N$. $N-1$ divise $L$. $A_i=\frac{L}{N-1}\times(i-1)$. |
| 4 | 20 | $L\le5\,000\,000$ |
| 5 | 35 | Aucune contrainte supplémentaire ne s’applique. |
Entrée
La première ligne contient trois entiers $L,N,K$, dans cet ordre, séparés par des espaces.
La ligne suivante contient $N$ entiers $A_1,\ldots,A_N$, dans cet ordre, séparés par des espaces.
Sortie
Affichez la réponse sur $K$ lignes à partir de la première. La $i$-ième ligne doit contenir la $i$-ième plus petite valeur d’obscurité.
Exemples
Entrée 1
10 3 4 1 4 8
Sortie 1
0 0 0 1
Entrée 2
4 5 5 0 1 2 3 4
Sortie 2
0 0 0 0 0
Entrée 3
7 1 4 3
Sortie 3
0 1 1 2
Entrée 4
9 4 10 0 3 6 9
Sortie 4
0 0 0 0 1 1 1 1 1 1