← 返回题目列表

Codeforces · 721/D

D. Maxim 和数组

中文机器翻译题面 查看原题

最近 Maxim 发现了一个由 n 个整数组成的数组,没有人需要。他立即想出了改变它的想法:他发明了正整数 x 并决定将其与任意数组元素相加或相减。形式上,通过应用单一运算,Maxim 选择整数 i (1 ≤ i ≤ n) 并将数组 ai 的第 i 个元素替换为 ai + x 或 ai - x。请注意,该操作可能会多次应用于同一位置。

Maxim 是一个好奇的极小主义者,因此他想知道如果 Maxim 对它应用不超过 k 次操作,所有数组元素(即 $$\prod_{i=1}^{n}a_{i}$$)的乘积可以达到的最小值是多少。请在这方面帮助他。

输入

输入的第一行包含三个整数 n、k 和 x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109)——分别是数组中的元素数量、最大运算次数和 Maxim 发明的数量。

第二行包含 n 个整数 a1, a2, ..., an ($${ \big | } a _ { i } { \big | } \leq 1 0 ^ { 9 }$$) — Maxim 找到的数组元素。

输出

在唯一的行中打印 n 个整数 b1, b2, ..., bn — 对数组应用不超过 k 个操作后的数组元素。特别是,$$a_i \equiv b_i \mod x$$ 对于每个 1 ≤ i ≤ n 应该保持为真,但所有数组元素的乘积应该尽可能最小。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

5 3 1
5 4 3 5 2

输出 #1

5 4 3 5 -1

输入 #2

5 3 1
5 4 3 5 5

输出 #2

5 4 0 5 5

输入 #3

5 3 1
5 4 4 5 5

输出 #3

5 1 4 5 5

输入#4

3 2 7
5 4 2

输出#4

5 11 -5