题目描述
译自 POI 2010 Stage 3. Day 1「Frog」
在 Byteotian 的小溪上有 n 个岩石在水位线上,这些岩石到源头的距离分别为 p1,p2,...,pn。在其中的一个岩石上有一只小青蛙准备开始训练。每一次,它会选择距离它第 k 近的岩石。严格地说,如果青蛙某时刻在 pi 位置,则它会选择 pj 位置使得同时满足:
∣pa:∣pa−pi∣<∣pj−pi∣∣≤k
∣pa:∣pa−pi∣≤∣pj−pi∣∣>k
如果这样的 pj 不唯一,则青蛙会选择距离源头最近的那一个。对每一个小青蛙初始时可能在的岩石,求 m 次跳跃后青蛙所在的位置。
输入格式
第一行有三个整数 n,k,m,用空格分隔,分别表示岩石的总数,参数 k,以及跳跃的次数。
第二行有 n 个整数 pj,用空格分隔,表示河面上岩石的位置。
输出格式
输出一行 n 个整数 r1,r2,...,rn,其中 ri 表示从第 i 个岩石开始连续跳跃 m 次后青蛙所在的位置。
样例
5 2 4
1 2 4 7 10
1 1 3 1 1
下图显示了从每个岩石开始经过一次跳跃到达的岩石。
数据范围与提示
对于 100% 的数据, 1≤k<n≤1000000,1≤m≤1018,1≤p1<p2<...<pn≤1018 。