A10640. 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.

The first line of the input contains three integers $n,k$ and $x$ ( $1<=n,k<=200000,1<=x<=10^{9}$ ) — 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.

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.