数直線で表される道路上に $N$ 本の街灯が点灯している。左から順に、その位置を $A_1<\cdots<A_N$ と表す。
位置 $x$ の暗さを、その位置から最も近い街灯までの距離と定義する。これは $N$ 個の数 $|A_1-x|,\ldots,|A_N-x|$ の最小値に等しい。ここで $|\cdot|$ は絶対値であり、$y\ge0$ なら $|y|:=y$、$y<0$ なら $|y|:=-y$ である。
例えば、$N=3$ 本の街灯が $A_1=1$、$A_2=4$、$A_3=8$ にある場合、$0$ から $10$ までの各整数位置の暗さは次のとおりである。
| 位置 | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 暗さ | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $2$ | $1$ | $0$ | $1$ | $2$ |
| 街灯があるか？ | O | O | O |
$x=0$ から $x=L$ までの $L+1$ 個すべての整数位置の暗さを求め、小さい方から $K$ 番目までの値を順に出力するプログラムを作成せよ。
制約
- 与えられる数はすべて整数である。
- $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$
小課題
| # | 得点 | 条件 |
|---|---|---|
| 1 | 10 | $N=1$ |
| 2 | 20 | $N\le2\,500$, $L\le2\,500$ |
| 3 | 15 | $2\le N$。$N-1$ は $L$ の約数である。$A_i=\frac{L}{N-1}\times(i-1)$。 |
| 4 | 20 | $L\le5\,000\,000$ |
| 5 | 35 | 追加制約はない。 |
入力
1 行目に 3 つの整数 $L,N,K$ が、この順に空白区切りで与えられる。
次の行に $N$ 個の整数 $A_1,\ldots,A_N$ が、この順に空白区切りで与えられる。
出力
1 行目から $K$ 行にわたって答えを出力せよ。$i$ 行目には小さい方から $i$ 番目の暗さを出力する。
入出力例
入力 1
10 3 4 1 4 8
出力 1
0 0 0 1
入力 2
4 5 5 0 1 2 3 4
出力 2
0 0 0 0 0
入力 3
7 1 4 3
出力 3
0 1 1 2
入力 4
9 4 10 0 3 6 9
出力 4
0 0 0 0 1 1 1 1 1 1