最近 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