题目描述

译自 POI 2010 Stage 3. Day 1「Frog」

在 Byteotian 的小溪上有 $n$ 个岩石在水位线上，这些岩石到源头的距离分别为 $p_1, p_2, ..., p_n$。在其中的一个岩石上有一只小青蛙准备开始训练。每一次，它会选择距离它第 $k$ 近的岩石。严格地说，如果青蛙某时刻在 $p_i$ 位置，则它会选择 $p_j$ 位置使得同时满足： $$|{p_a:|p_a-p_i|<|p_j-p_i|}| \le k$$ $$|{p_a:|p_a-p_i|\le|p_j-p_i|}| \gt k$$ 如果这样的 $p_j$ 不唯一，则青蛙会选择距离源头最近的那一个。对每一个小青蛙初始时可能在的岩石，求 $m$ 次跳跃后青蛙所在的位置。

输入格式

第一行有三个整数 $n,k,m$，用空格分隔，分别表示岩石的总数，参数 $k$，以及跳跃的次数。

第二行有 $n$ 个整数 $p_j$，用空格分隔，表示河面上岩石的位置。

输出格式

输出一行 $n$ 个整数 $r_1, r_2, ..., r_n$，其中 $r_i$ 表示从第 $i$ 个岩石开始连续跳跃 $m$ 次后青蛙所在的位置。

样例

input

5 2 4
1 2 4 7 10

output

1 1 3 1 1

下图显示了从每个岩石开始经过一次跳跃到达的岩石。

数据范围与提示

对于 $100\%$ 的数据， $1 \le k \lt n \le 1000000, 1 \le m \le 10^{18} , 1 \le p_1 \lt p_2 \lt ... \lt p_n \le 10^{18}$ 。