An einer als Zahlengerade dargestellten Straße leuchten $N$ Straßenlaternen. Ihre Positionen von links nach rechts sind $A_1<\cdots<A_N$.
Die Dunkelheit an Position $x$ sei der Abstand von dieser Position zur nächsten Straßenlaterne. Sie ist das Minimum der $N$ Zahlen $|A_1-x|,\ldots,|A_N-x|$. Dabei bezeichnet $|\cdot|$ den Absolutbetrag: $|y|:=y$ für $y\ge0$ und $|y|:=-y$ für $y<0$.
Wenn beispielsweise $N=3$ Straßenlaternen an $A_1=1$, $A_2=4$ und $A_3=8$ stehen, ergibt sich die folgende Dunkelheit an jeder ganzzahligen Position von $0$ bis $10$.
| Position | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Dunkelheit | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $2$ | $1$ | $0$ | $1$ | $2$ |
| Laterne vorhanden? | O | O | O |
Schreibe ein Programm, das die Dunkelheit an allen $L+1$ ganzzahligen Positionen von $x=0$ bis $x=L$ berechnet und die Werte der Reihe nach vom kleinsten bis zum $K$-kleinsten ausgibt.
Beschränkungen
- Alle gegebenen Zahlen sind ganzzahlig.
- $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$
Teilaufgaben
| # | Punkte | Bedingung |
|---|---|---|
| 1 | 10 | $N=1$ |
| 2 | 20 | $N\le2\,500$, $L\le2\,500$ |
| 3 | 15 | $2\le N$. $N-1$ teilt $L$. $A_i=\frac{L}{N-1}\times(i-1)$. |
| 4 | 20 | $L\le5\,000\,000$ |
| 5 | 35 | Es gibt keine zusätzlichen Beschränkungen. |
Eingabe
Die erste Zeile enthält drei ganze Zahlen $L,N,K$ in dieser Reihenfolge, getrennt durch Leerzeichen.
Die nächste Zeile enthält $N$ ganze Zahlen $A_1,\ldots,A_N$ in dieser Reihenfolge, getrennt durch Leerzeichen.
Ausgabe
Gib die Antwort ab der ersten Zeile in $K$ Zeilen aus. In der $i$-ten Zeile muss der $i$-kleinste Dunkelheitswert stehen.
Beispiele
Eingabe 1
10 3 4 1 4 8
Ausgabe 1
0 0 0 1
Eingabe 2
4 5 5 0 1 2 3 4
Ausgabe 2
0 0 0 0 0
Eingabe 3
7 1 4 3
Ausgabe 3
0 1 1 2
Eingabe 4
9 4 10 0 3 6 9
Ausgabe 4
0 0 0 0 1 1 1 1 1 1