CF721D.Maxim and Array

Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array a__i either with a__i + x or with a__i - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. ) can reach, if Maxim would apply no more than k operations to it. Please help him in that.

最近，马克西姆发现了一个由 $ n $ 个整数组成的数组，而这个数组对任何人都没有用处。他立刻萌生了修改它的想法：他构造了一个正整数 $ x $，并决定对数组中的任意元素加上或减去 $ x $。形式上，每次操作中，马克西姆选择一个下标 $ i $（$ 1 \leq i \leq n $），并将数组的第 $ i $ 个元素 $ a_i $ 替换为 $ a_i + x $ 或 $ a_i - x $。请注意，同一位置可以被多次执行该操作。

马克西姆是一位充满好奇心的极简主义者，因此他想知道：若最多执行 $ k $ 次操作，数组所有元素的乘积（即 ）所能达到的最小值是多少？请帮助他解决这个问题。

The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers _a_1, _a_2, ..., a__n () — the elements of the array found by Maxim.

输入的第一行包含三个整数 $n$、$k$ 和 $x$（$1 \leq n, k \leq 200\,000$，$1 \leq x \leq 10^9$）——分别表示数组的元素个数、最多可执行的操作次数，以及 Maxim 构造出的数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（）——即 Maxim 找到的数组元素。

Print n integers _b_1, _b_2, ..., b__n in the only line — the array elements after applying no more than k operations to the array. In particular, should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.

在一行中输出 n 个整数 _b_₁, _b_₂, ..., b__n —— 即对数组执行不超过 k 次操作后所得的数组元素。特别地，对每个 1 ≤ i ≤ n，都应满足 ，但此时整个数组所有元素的乘积应尽可能小。

若存在多个合法答案，输出任意一个即可。