题目描述

在一条特别长直的 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 $$

如果有多个满足条件的岩石，青蛙会选择距离泉水更近的那个岩石。请确定青蛙经过 $m$ 次跳跃后停在哪个岩石上，初始岩石的位置为 $i$。

输入格式

第一行包含三个整数 $n, k, m$ ($1 \le k < n \le 1 \, 000 \, 000, 1 \le m \le 10^{18}$)，分别表示岩石的数量，跳跃条件 $k$，和跳跃次数 $m$。

第二行包含 $n$ 个整数 $p_j$ ($1 \le p_1 < p_2 < \cdots < p_n \le 10^{18}$)，表示每个岩石的位置。

输出格式

输出一行包含 $n$ 个整数，表示每只青蛙经过 $m$ 次跳跃后最终停在哪个岩石上的编号。

5 2 4
1 2 4 7 10

1 1 3 1 1

提示

样例 #1 解释：