3281. [POI 2010] ZAB-Frog

【题目描述】

在一个特别长且笔直的 Byteotian 小溪的河床上，有 $n$ 块石头露出水面。它们距离小溪源头的距离分别为 $p_1 < p_2 < \cdots < p_n$。一只小青蛙正坐在其中一块石头上，准备开始它的跳跃训练。每次青蛙跳跃到距离它所在石头第 $k$ 近的石头上。具体来说，如果青蛙坐在位置 $p_i$ 的石头上，那么它将跳到这样的 $p_j$ 上，使得：

$|\{ p_a : |p _ a - p _ i| < |p_j - p_i| \}| \le k \text{ and } |\{ p_a : |p _ a - p _ i| \le |p_j - p_i| \}| > k$

如果 $p_j$ 不是唯一的，那么青蛙在其中选择距离源头最近的石头。对于每一块石头分别计算，若青蛙从这块石头开始跳跃，经过 $m$ 次跳跃后最终会停留在哪一块石头上？

【输入格式】

第一行包含三个整数 $n$、$k$ 和 $m$（$1 \le k < n \le 1\,000\,000, 1 \le m \le 10^{18}$），用空格分隔，分别表示石头的数量、参数 $k$ 和计划跳跃的次数。第二行包含 $n$ 个整数 $p_j$（$1 \le p_1 < p_2 < \cdots < p_n \le 10^{18}$），用空格分隔，表示小溪河床上连续石头的位置。

【输出格式】

一行，包含 $n$ 个整数 $r_1, r_2, \cdots, r_n$，用空格分隔。数字 $r_i$ 表示从输入顺序中的第 $i$ 块石头开始跳跃 $m$ 次后，青蛙最终停留的石头编号。

【样例输入】

5 2 4
1 2 4 7 10

【样例输出】

1 1 3 1 1