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.

Input

The first line of the input contains three integers $*n*, *k*$ and $*x*$ ($1 ≤ *n*, *k* ≤ 200 000, 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.

Output

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.